Description
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 <= 2000sconsists of lowercase English letters only.
Solution
Python3
class Solution:
def minCut(self, s: str) -> int:
if len(s) == 1: return 0
n = len(s)
dp = list(range(n))
for mid in range(1, n):
start = end = mid
while start >= 0 and end < n and s[start] == s[end]:
cut = 0 if start == 0 else dp[start - 1] + 1
dp[end] = min(dp[end], cut)
start -= 1
end += 1
start, end = mid - 1, mid
while start >= 0 and end < n and s[start] == s[end]:
cut = 0 if start == 0 else dp[start - 1] + 1
dp[end] = min(dp[end], cut)
start -= 1
end += 1
return dp[-1]