Leetcode 132. Palindrome Partitioning II

Seawolf

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 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:

Input: s = "a"
Output: 0
Example 3:

Input: s = "ab"
Output: 1


Constraints:

1 <= s.length <= 2000
s consists of lower-case English letters only.

class Solution:
    def minCut(self, s: str) -> int:
        if s == None or len(s) == 0:
            return 0
        
        # optimize 0-cut and 1-cut
        if s == s[::-1]: return 0
        for i in range(1, len(s)):
            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                return 1
        
        # normal case
        dp = [math.inf for _ in range(len(s) + 1)]
        dp[0] = 0
        
        def cal_palindrome():
            palindrome = [[False for _ in s] for _ in s]
            N = len(s)
            
            # Odd
            for i in range(N):
                left = right = i
                while left >= 0 and right < N and s[left] == s[right]:
                    palindrome[left][right] = True
                    left -= 1
                    right += 1
            
            # Even
            for i in range(N):
                left, right = i, i + 1
                while left >= 0 and right < N and s[left] == s[right]:
                    palindrome[left][right] = True
                    left -= 1
                    right += 1
            return palindrome
        
        palindrome = cal_palindrome()            
        
        for i in range(1, len(s) + 1):
            for j in range(i):
                if palindrome[j][i - 1]:
                    dp[i] = min(dp[i], dp[j] + 1)
        
        # number of cut equals to number of palindrome - 1
        return dp[len(s)] - 1