原题
给定一个字符串s，将s分割成一些子串，使每个子串都是回文。
返回s符合要求的的最少分割次数。
比如，给出字符串s =** "aab"**，
返回 1， 因为进行一次分割可以将字符串s分割成["aa","b"]这样两个回文子串
解题思路
- 序列型动态规划 - Sequence DP
- cache[i]表示前i个字符组成的字符串需要最少cut几次保证子串都是回文串(或能被分割成多少个回文串 - 1)
- 初始化cache[i] = i -1
- cache[0] = -1 (因为前0个字符串被分割成0个回文串，0 - 1 = -1)
- 状态转移方程：cache[i] = min(cache[j] + 1)
满足条件的j应该是 - j < i
- j+1 ~ i 这一段是回文串
- 对于判断某一段是否是回文串，使用区间型动态规划可以将时间复杂度从O(n)优化到O(1)
二维数组缓存判断结果
完整代码
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
IsPalindrome = self.getIsPalindrome(s)
cache = [0 for _ in range(len(s) + 1)]
for i in range(len(s) + 1):
cache[i] = i - 1
for i in range(1, len(s) + 1):
for j in range(i):
if IsPalindrome[j][i - 1]:
cache[i] = min(cache[i], cache[j] + 1)
return cache[len(s)]
def getIsPalindrome(self, str):
IsPalindrome = [[False for i in range(len(str))] for i in range(len(str))]
"""
initialize (0, 0), (1, 1)......
and (0, 1), (1, 2)......
"""
for i in range(len(str)):
IsPalindrome[i][i] = True
for i in range(len(str) - 1):
if str[i] == str[i + 1]:
IsPalindrome[i][i + 1] = True
for length in range(2, len(str)):
for start in range(0, len(str) - length):
IsPalindrome[start][start + length] = \
IsPalindrome[start + 1][start + length - 1] and str[start] == str[start + length]
return IsPalindrome
