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()];
}
}
