132. Palindrome Partitioning II

Problem Statement

link: https://leetcode.com/problems/palindrome-partitioning-ii/ https://leetcode.cn/problems/palindrome-partitioning-ii/

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: s = "aab" Output: 1

Input: s = "a" Output: 0

Input: s = "ab" Output: 1

Solution Approach

The solution leverages dynamic programming to precompute palindromic substrings and subsequently calculate the minimum cuts needed for each character in the string.

Algorithm

1. Palindrome Precomputation: Construct a 2D boolean matrix (is_pal) to determine if substrings between indices (i, j) are palindromes.
2. DP Initialization: Formulate a 1D DP array (dp) with dp[i] signifying the minimal cuts needed for the substring leading up to index i.
3. DP Transition: For each character, if its substring is a palindrome, set its dp value to 0; otherwise, iterate through previous characters to update its value based on prior minimum cuts and palindrome checks.

Implement

    class Solution:
      def minCut(self, s: str) -> int:
          n = len(s)
          is_pal = [[True] * n for _ in range(n)]

          for i in range(n - 1, -1, -1):
              for j in range(i + 1, n):
                  is_pal[i][j] = (s[i] == s[j]) and is_pal[i + 1][j - 1]
          dp = [n] * n
          for i in range(n):
              if is_pal[0][i]:
                  dp[i] = 0
                  continue
              for j in range(i):
                  if is_pal[j + 1][i]:
                      dp[i] = min(dp[i], dp[j] + 1)
          return dp[n - 1]

    
    

Twitter  facebook  Email