Leetcode 132. Palindrome Partitioning II
本帖最后由 Seawolf 于 2020-9-24 02:14 编辑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 == s[::-1]:
return 1
# normal case
dp =
dp = 0
def cal_palindrome():
palindrome = [ for _ in s]
N = len(s)
# Odd
for i in range(N):
left = right = i
while left >= 0 and right < N and s == s:
palindrome = True
left -= 1
right += 1
# Even
for i in range(N):
left, right = i, i + 1
while left >= 0 and right < N and s == s:
palindrome = 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:
dp = min(dp, dp + 1)
# number of cut equals to number of palindrome - 1
return dp - 1
页:
[1]