LeetCode 132 [Palindrome Partitioning II]

原题

给定一个字符串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