Palindrome Partitioning II

Question

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Sample

Given s = "aab",

Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.

Solution:

这道题重点在于构造一个区间型的动态规划，isPalin[i, j] 表示从第i个字符到第j个字符是否是回文字符串。

class Solution:
    # @param s, a string
    # @return an integer
    def minCut(self, s):
        # write your code here
        n = len(s) 
        #建议一个区间型的动态规划，表示从i 到 j是否是回文
        isPalin = [[False for x in range(n)] for y in range(n)]
        f = [0 for x in range(n + 1)]
        #, a, or ab 考虑单个或者两个
        for i in range(n):
            isPalin[i][i] = True # 对角线表示，从i到i，所以肯定True
            if i + 1 < n:
                isPalin[i][i+1] = (s[i] == s[i + 1])

        # more than 3 letters
        for i in range(n - 1, -1, -1):
            for j in range(i + 2, n):
                isPalin[i][j] = isPalin[i + 1][j - 1] and s[i] == s[j]
        #从大于2个开始


        f[0] = -1 #|aaa F[""] + 1 => 0 then F[""] = -1
        for i in range(1, n + 1):
            f[i] = i - 1 #abcd i = 4 , i -3 = 3 刀
            for j in range(i): 
                #从后往前面切，
                if isPalin[j][i-1]:
                    f[i] = min(f[i], f[j] + 1)
        return f[n]