108. 分割回文串 II

中文English

给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串.

最少需要分割几次?

样例

样例 1:

输入: "a"
输出: 0
解释: "a" 本身就是回文串, 无需分割

样例 2:

输入: "aab"
输出: 1
解释: 将 "aab" 分割一次, 得到 "aa" 和 "b", 它们都是回文串.

大致思路： 动态规划 l = len(s) 1.确定状态 最后一步:d[l-1] 子问题:d[i-1] = min(dj] + 1,d[i-1])
2.转移方程 d[i] = min(d[j] + 1 , d[i])
3.初始条件和边界情况 d = [sys.maxsize]*(l+1) d[0] = 0
存在一种边界情况，是aaaaa这种，一直都是0，不同于bbbaa，bbb + aa 需要加1 if s[:i] == s[:i][::-1]:     d[i] = 0 　continue
current_s = s[j:i] if current_s == current_s[::-1]
4.计算顺序 for i in range(1,l+1):     for j in range(i):         if s[j:i] == s[j:i][::-1]: 　　

class Solution:
    """
    @param s: A string
    @return: An integer
    """
    def minCut(self, s):
        # write your code here
        if not s:return 0 
        
        #初始条件
        l = len(s)
        d = [sys.maxsize]*(l+1)
        d[0] = 0

        #计算顺序
        for i in range(1,l+1):
            if s[:i] == s[:i][::-1]:
                d[i] = 0
                continue

            for j in range(i):
                cut_s = s[j:i]

                #边界情况
                if cut_s == cut_s[::-1]:
                    d[i] = min(d[j] + 1,d[i])
        return d[l]