LeetCode - Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.For example, given s = "aab",

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

首先设置dp变量 cuts[len+1]。cuts[i]表示从第i位置到第len位置（包含，即[i, len])的切割数（第len位置为空）。

初始时，是len-i。比如给的例子aab，cuts[0]=3，就是最坏情况每一个字符都得切割：a|a|b|' '。cuts[1] = 2, 即从i=1位置开始，a|b|' '。

cuts[2] = 1 b|' '。cuts[3]=0,即第len位置，为空字符，不需要切割。

上面的这个cuts数组是用来帮助算最小cuts的。

还需要一个dp二维数组matrixs[i][j]表示字符串[i,j]从第i个位置（包含）到第j个位置（包含） 是否是回文。

如何判断字符串[i,j]是不是回文？

1. matrixs[i+1][j-1]是回文且 s.charAt(i) == s.charAt(j)。

2. i==j（i，j是用一个字符）

3. j=i+1（i，j相邻）且s.charAt(i) == s.charAt(j)

当字符串[i,j]是回文后，说明从第i个位置到字符串第len位置的最小cut数可以被更新了，

那么就是从j+1位置开始到第len位置的最小cut数加上[i,j]|[j+1,len - 1]中间的这一cut。

即，Math.min(cuts[i], cuts[j+1]+1) 

最后返回cuts[0]-1。把多余加的那个对于第len位置的切割去掉，即为最终结果。

public int minCut(String s) {
    if(s==null||s.length()<=1) return 0;
    int n = s.length();
    int[] cuts = new int[n+1];
    boolean[][] palin = new boolean[n][n];
    for(int i=0; i<n; i++) {
        cuts[i] = n-i;
    }
    for(int i=n-1; i>=0; i--) {
        for(int j=i; j<n; j++) {
            if(s.charAt(i)==s.charAt(j) && (j-i<2 || palin[i+1][j-1])) {
                palin[i][j] = true;
                cuts[i] = Math.min(cuts[i], cuts[j+1]+1);
            }
        }
    }
    return cuts[0]-1;
}

 

还有另外一种写法。

palin[i][j]表示字符串s的子串s[i...j]是否为回文串，cuts[j]表示子串s[0...j]所需要的最小分割数。

public int minCut(String s) {
    if(s==null||s.length()<=1) return 0;
    int n = s.length();
    int[] cuts = new int[n];
    boolean[][] palin = new boolean[n][n];
    for(int j=0; j<n; j++) {
        cuts[j] = j;
        for(int i=0; i<=j; i++) {
            //如果子串 s[i...j]是回文串
            if(s.charAt(i)==s.charAt(j) && (j-i<=1 || palin[i+1][j-1])) {
                palin[i][j] = true;
                //如果 s[0...j]是回文串，则说明不需要切割
                cuts[j] = Math.min(cuts[j], i>0 ? cuts[i-1]+1 : 0);
            }
        }
    }
    return cuts[n-1];
}

 

LeetCode上还有一个更好的解法，不需要使用二维数组来保存是否为回文：

https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space

public int minCut(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    
    int[] cut = new int[n+1];  // number of cuts for the first k characters
    for (int i = 0; i <= n; i++) cut[i] = i-1; // initialize cuts to worst
    
    for (int i = 0; i < n; i++) {
        // odd length palindrome
        for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) {
            cut[i+j+1] = Math.min(cut[i+j+1],1+cut[i-j]);
        }
        // even length palindrome
        for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) {
            cut[i+j+1] = Math.min(cut[i+j+1],1+cut[i-j+1]);
        }
    }
    
    return cut[n];
}

 

上述代码还是不好理解，我每次都要花好长时间才能理解。又重构了下代码，下面这个是目前最好理解的写法：

public int minCut(String s) {
    int n = s.length();
    if(n <= 1) return 0;
    int[] f = new int[n+1];
    for(int i=0; i<=n; i++) f[i] = i-1; // worst case
    
    for(int i=0; i<n; i++) {
        // odd length palindrome
        for(int l=i, r=i; l>=0 && r<n && s.charAt(l) == s.charAt(r); l--, r++) {
            f[r+1] = Math.min(f[r+1], f[l] + 1);
        }
        // even length palindrome
        for(int l=i, r=i+1; l>=0 && r<n && s.charAt(l) == s.charAt(r); l--, r++) {
            f[r+1] = Math.min(f[r+1], f[l] + 1);
        }
    }
    return f[n];
}

  

Reference:

http://www.cnblogs.com/springfor/p/3891896.html

http://www.acmerblog.com/palindrome-partitioning-ii-6148.html

http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning-ii.html