Palindrome Partitioning II
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 <= 2000
s
consists of lowercase English letters only.
Solution(python3)
class Solution:
def minCut(self, s: str) -> int:
length = len(s)
cuts = [i for i in range(length)]
for i in range(length):
# Odd size palindrome
j = 0 # one-character palindrome when j == 0
while i - j >= 0 and i + j < length and s[i - j] == s[i + j]:
prev_cuts = cuts[i - j - 1] if i - j - 1 >= 0 else -1
cuts[i + j] = min(cuts[i + j], prev_cuts + 1)
j += 1
# Even size palindrome
j = 0
while i - j >= 0 and i + j + 1 < length and s[i - j] == s[i + j + 1]:
prev_cuts = cuts[i - j - 1] if i - j - 1 >= 0 else -1
cuts[i + j + 1] = min(cuts[i + j + 1], prev_cuts + 1)
j += 1
return cuts[-1]