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.

1. class Solution:
   
2.     def minCut(self, s: str) -> int:
   
3.         if s == None or len(s) == 0:
   
4.             return 0
   
5.         
   
6.         # optimize 0-cut and 1-cut
   
7.         if s == s[::-1]: return 0
   
8.         for i in range(1, len(s)):
   
9.             if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
   
10.                 return 1
    
11.         
    
12.         # normal case
    
13.         dp = [math.inf for _ in range(len(s) + 1)]
    
14.         dp[0] = 0
    
15.         
    
16.         def cal_palindrome():
    
17.             palindrome = [[False for _ in s] for _ in s]
    
18.             N = len(s)
    
19.             
    
20.             # Odd
    
21.             for i in range(N):
    
22.                 left = right = i
    
23.                 while left >= 0 and right < N and s[left] == s[right]:
    
24.                     palindrome[left][right] = True
    
25.                     left -= 1
    
26.                     right += 1
    
27.             
    
28.             # Even
    
29.             for i in range(N):
    
30.                 left, right = i, i + 1
    
31.                 while left >= 0 and right < N and s[left] == s[right]:
    
32.                     palindrome[left][right] = True
    
33.                     left -= 1
    
34.                     right += 1
    
35.             return palindrome
    
36.         
    
37.         palindrome = cal_palindrome()            
    
38.         
    
39.         for i in range(1, len(s) + 1):
    
40.             for j in range(i):
    
41.                 if palindrome[j][i - 1]:
    
42.                     dp[i] = min(dp[i], dp[j] + 1)
    
43.         
    
44.         # number of cut equals to number of palindrome - 1
    
45.         return dp[len(s)] - 1

复制代码