Palindrome Partitioning II

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.

(注：写的废话有点多，可以直接看我在leetcode discuss的提问https://oj.leetcode.com/discuss/24253/how-to-get-from-o-n-3-to-o-n-2-java-solution-sharing）
Naive Way: 好像有上一题的DP的二维矩阵就可以很快得到最小割了。

基本一致的回溯方式，这样的算法复杂度是O(2^n)，最坏的情况。然后会出现超时。

public class Solution {
    public int minCut(String s) {
        boolean opt[][] = new boolean[s.length()][s.length()+1];
        // base case
        for(int i = 0;i < s.length();i++){
            opt[i][i+1] = true;
            opt[i][i] = true;
        }
        // iteration
        for(int i = 2;i <= s.length();i++)
            for(int j = 0;j+i <= s.length();j++)
                opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1];
        
        return search(0,opt,-1);
    }
    
    private int search(int begin, boolean[][] opt, int cut){
        int min = opt[0].length;
        if(begin==opt[0].length-1)
            return cut;
        for(int i = begin+1;i < opt[0].length;i++)
            if(opt[begin][i])
                min = Math.min(search(i,opt,cut+1),min);
        return min;
    }
}


Improved Way:这时我想到O(n)求longest palindrome substring的方法。因为那个方法能在O(n)的时间内求出所有字符的覆盖范围，那么用贪心的思想取覆盖范围大的，就可以实现最小分割数了。

实际做时，发现这种greedy的思想会产生一个bug。当String = aaaba的时候。
0  1  2  3  4  5  6  7  8  9  10
#  a  #  a   #  a  #  b  #  a  #
1  2  3  4  3  2  1  4  1  2  1

先取第一个4就会得到{"aaa","b","a"}
先取第二个4就会得到{"aa","aba"}
一个是3割一个是2割。
这个BUG只会在OJ的倒数第二种测例中出现，很容易忽略。同时，这个例子也可以说明对DP的结果进行遍历时，不能够用greedy的思想去最大长度的找一个max(j-i) 其中 opt[i][j]=true。否则就会出现这里这种先找前3个a而导致后面必须用多一个割的情况。



这时看了一眼这道题的标签，是DP耶。幡然醒悟，应该用一个更直接的DP。
基本逻辑为：
opt(i,j) //表示将String s[i-j]分成全palindrome子串的最少割数。
// base case
opt(i,i) = 0     0<= i < s.length()
// iteration
opt(i,j) =
if s[i]==s[j] && opt(i+1,j-1)==0
     0
else
     min(opt(i,t)+opt(t+1,j)+1)  for  i<= t < j

算法复杂度为O(n^3)，但还是超时了。
public class Solution {
    public int minCut(String s) {
        // DP
        int opt[][] = new int[s.length()][s.length()];
        // base case 0
        // iteration
        for(int i = 1;i < s.length();i++){
            for(int j = 0;j+i < s.length();j++){
                if(s.charAt(j)==s.charAt(j+i) && opt[j+1][j+i-1]==0){
                    opt[j][j+i] = 0;
                }else{
                    opt[j][j+i] = i;
                    for(int t = j;t < j+i;t++)
                        opt[j][j+i] = Math.min(opt[j][j+i], opt[j][t]+opt[t+1][j+i]+1);
                }
            }
        }
        return opt[0][s.length()-1];
    }
}


可以不可以在O(n^2)内完成呢？如果DP只有一个参数呢？
opt[i] // 表示分割s[0-i]所需最小分割数。
 // base case
opt[0] = 0;
// iteration
opt[i] =
if(s[0-i] is palindrome)
     0
else
    min(opt[t] + s[t+1 ~ i] is palindrome?1:i-t)

这样做虽然只有O(n)的外层循环，但是每一次循环都要遍历之前所有还要同时判断当前的是否为palindrome,每一次循环就需要O(n^2)，所以还是O(n^3)。

还是看了一下discuss发现自己好愚蠢，在一开始就已经在O(n^2)的时间内求出所有s[i~j]是否为palindrome了。所以每一层循环现在只需要O(n)的时间，总的时间就是O(n^2)了。


public class Solution {
    public int minCut(String s) {
        // use DP to determine any palindrome substring
        boolean opt[][] = new boolean[s.length()][s.length()+1];
        // base case
        for(int i = 0;i < s.length();i++){
            opt[i][i+1] = true;
            opt[i][i] = true;
        }
        // iteration
        for(int i = 2;i <= s.length();i++)
            for(int j = 0;j+i <= s.length();j++)
                opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1]; 
        
        
        // use DP to determine min cut
        int cut[] = new int[s.length()+1];
        for(int i = 1;i <= s.length();i++){
            if(opt[0][i])
                cut[i] = 0;
            else{
                cut[i] = i-1;
                for(int t = 1;t < i;t++){
                    cut[i] = Math.min(cut[i],cut[t] + (opt[t][i]?1:i-t));
                }
            }
        }
        return cut[s.length()];
        
    }
}