LeetCode刷题实战132:分割回文串 II
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.
题意
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
解题
dp[i-1]
为子串s[0:i-1]
(前闭后闭)的最小分割次数,推出dp[i]
的转移方程。首先,如果
s[0:i]
本身是一个回文串,那么不需要分割,dp[i] = 0
;如果
s[0:i]
不是回文串,那么我们需要枚举以s[i]
结尾的回文串,从1
到i
的索引j
,判断s[j:i]
是不是回文串,如果是,则dp[i]=dp[j-1]+1
,即在前j-1
个字符串的基础上多一次切割。枚举所有可能的j
,取最小值。不可以逐次判断是否是回文串,会超时,因此回文串的判断也采取动态规划的思想。如果一个字符串
s[i:j]
是回文串,那么其子串s[i+1:j-1]
也是回文串。因此,dp[i][j]
表示子串s[i:j]
是否是回文串,我们枚举字符串子串的长度,再枚举子串的起始位置,填充dp。
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
l = len(s)
dpPart = [[False]*l for _ in range(l)]
dp = [i for i in range(l)]
# 判断回文串,填充dpPart
# 枚举子串长度
for length in range(l):
# 枚举子串开始位置,length==0表示子串长度为1
for i in range(l):
j = i + length
if j >= l:
break
if length == 0:
dpPart[i][j] = True
elif length == 1:
dpPart[i][j] = (s[i] == s[j])
else:
dpPart[i][j] = dpPart[i+1][j-1] and (s[i] == s[j])
# 填充dp
for i in range(1, l):
if dpPart[0][i]:
dp[i] = 0
continue
for j in range(1, i+1):
# 枚举以s[i]结尾的回文串
if (dpPart[j][i]):
dp[i] = min(dp[i], dp[j - 1] + 1)
return dp[l - 1]