132. Palindrome Partitioning II

# Hard （很有意义很经典的一道动态规划的题，可以同时有两个动态规划来优化时间复杂度）

This link is the best solution improvement pathway.

https://leetcode.com/problems/palindrome-partitioning-ii/discuss/668367/Java-3-Versions-Of-The-Solusions.-Easy-to-understand!!

Solution:

1. Initilize p[i][j] = False, which represents whether the substring [i:j] of the string is palindrome.

2. Initilize minCut[i] = i, which represents the minimum cut of the substring ends at i.

3. If p[i][j] = True, then minCut[i] = min(minCut[i], minCut[j-1] + 1). We can find at least one palindrome until index of i, because any character is palindrome.

4. Return minCut[len(s)-1]

Python

class Solution:
    def minCut(self, s: str) -> int:
        p = [[False]*len(s) for i in range(len(s))]
        minCut = [i for i in range(len(s))]
        # self.isPalin(s, p)
        
        for i in range(1, len(s)):
            for j in range(0, i+1):
                if s[i] == s[j] and (j+1 >= i-1 or p[j+1][i-1] == True):
                    p[j][i] = True
                    if j == 0:
                        minCut[i] = 0
                        break
                    else:
                        minCut[i] = min(minCut[i], minCut[j-1]+1)
        
        return minCut[len(s)-1]
        
  # 计算 string 中从 j 到 i 是否是回文，用p[j][i]表示      
    def isPalin(self, s, p):
        for i in range(len(s)):
            for j in range(i+1):
                if i == j: 
                    p[j][i] = True
                else:
                    if s[j] == s[i]:
                        if j+1 >= i-1 or p[j+1][i-1] == True:
                            p[j][i] = True

Java(O(n^2)

class Solution {
    public int minCut(String s) {
        int[] minCut = new int[s.length()];
        for(int i = 0; i < s.length(); i ++) {
            minCut[i] = i;
        }
        
        boolean[][] palind = new boolean[s.length()][s.length()];
        
        fillPalind(s, palind);
        
        for(int i = 1; i < s.length(); i ++)
            for(int j = 0; j <= i; j ++) {
                if(palind[j][i]) {
                    if(j == 0) {
                        minCut[i] = 0;
                        break;
                    } else {
                        minCut[i] = Math.min(minCut[i], minCut[j-1]+1);
                    }
                }
            }
        return minCut[s.length() - 1];
    }
    
    private void fillPalind(String s, boolean[][] palind) {
        for(int i = 0; i < s.length(); i ++)
            for(int j = 0; j <= i; j ++ ) {
                if(i == j)
                    palind[j][i] = true;
                else if(s.charAt(j) == s.charAt(i)) {
                    if(j+1 >= i-1 || palind[j+1][i-1] == true)
                        palind[j][i] = true;
                }
            }
    }
}      

这里有两部需要注意的：

第一步：计算一个string所有子字符串是否是回文。优化一：事先计算好所有的，这样的时间复杂度虽然是 $O(n^2)$ ，但是在第二步中只需要获取这步的结果，比直接在第二步的每次循环中去检查子字符串是否是回文用的时间复杂度 $O(n^3)$ 要快得多；优化二：用动态规划来计算是否为回文的矩阵，如果这个字符串开头与结尾字符相等，并且中间的字符串为回文（根据之前的记录），那么这个子字符串就是回文；优化三：由于都是两层的循环，因此可以将计算回文与最小cut同步进行，这样节省了一倍的时间。

第二步：用动归计算从第一个字母开始的[i:j]最小cut，也就是说一个字符串，如果可以从中间切一刀，右半部分是回文，那么这个位置的minCut就是cut之前那个元素的minCut加一，循环来寻找最小值