Posted on 2013-04-11 11:24
小明 閱讀(4142)
評論(3) 編輯 收藏 所屬分類:
數據結構和算法
解法一：【遞歸】
對于一個字符串，先找到第一段回文子字符串，然后再求余下的子串的最少分割數，然后再加1，就可以得到一種分割結果，遍歷所以這樣的解法，就可以求出最小的分割次數。
public class MinCut {
private boolean isPalindrome(String s){
int len = s.length();
if(len>1){
for(int i=0;i<len/2;++i){
if(s.charAt(i)!=s.charAt(len-i-1)){
return false;
}
}
}
return true;
}
public int minCut(String s){
if(isPalindrome(s)){
return 0;
}
int min = 99999;
int len =s.length();
for(int i=1;i<len;++i){
String ss = s.substring(0,i);
if(isPalindrome(ss)){
int result = minCut(s.substring(i))+1;
if(result<min){
min = result;
}
if(min<=1){
break;
}
}
}
return min;
}
public static void main(String[] args) throws IOException {
long tick = System.currentTimeMillis();
MinCut m = new MinCut();
int result = m.minCut("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
System.out.println("result:"+result+",costs:"+(System.currentTimeMillis()-tick)+" ms");
}
}
這樣算法雖然可行，但是效率很低，對于小字符串還可以工作，對于上面的長度為1400+的字符串就慢的驚人。
因為有大量的重復計算。改進一下，把已經計算好的子串的最少分割次數的結果記錄下來，應該能快很多。
Map<String,Integer> memos = new HashMap<String,Integer>();
public int cut(String s){
if(isPalindrome(s)){
return 0;
}
if(memos.containsKey(s)){
return memos.get(s).intValue();
}
int min = 99999;
int len =s.length();
for(int i=1;i<len;++i){
String ss = s.substring(0,i);
if(isPalindrome(ss)){
int result = cut(s.substring(i))+1;
if(result<min){
min = result;
}
if(min<=1){
break;
}
}
}
memos.put(s, min);
return min;
}
public int minCut(String s) {
memos.clear();
return cut(s);
}
果然，優化后的結果要快很多，在我的機器上大概1200ms就可以求出結果了。
解法二：【動態規劃】
其實這個問題是一個典型的動態規劃問題。問題的最優解可以歸結為兩個子問題的最優解，再加上1就可以了，使用動態規劃記錄所有的中間狀態就可以降低重復計算。
狀態轉移公式如下：
minCut(s,i,j) = 0 if(s[i..j] 是回文的）
minCut(s,i,j) = min(minCut(s,i,k)+minCut(s,k+1,j))(i<k<j) |
為了減少回文的判斷，使用了兩個數組，M用來記錄最優分割次數，P用來保存子串的回文判斷結果。
代碼如下：
public int minCut(String s){
int totalLength = s.length();
char[] ch=s.toCharArray();
int [][] M = new int[totalLength][totalLength];
boolean [][] P = new boolean[totalLength][totalLength];
for(int len=1;len<=totalLength;++len){
for(int i=0;i<totalLength-len+1;++i){
int j = i+len-1;
if(len==1){
P[i][j]=true;
}
else if(len==2){
P[i][j]=(ch[i]==ch[j]);
}
else{
P[i][j]=(ch[i]==ch[j]) && P[i+1][j-1];
}
if(P[i][j]){
M[i][j] = 0;
}
else{
int min = 99999;
for(int k=i;k<j;++k){
int t = M[i][k]+M[k+1][j]+1;
if(min>t){
min = t;
}
}
M[i][j] = min;
}
}
}
return M[0][totalLength-1];
}
這個算法的復雜度是O(n
3）的復雜度，使用了三層循環。對于上面的字符串大概需要花4000ms左右的時間。
有沒有辦法把復雜度降為O(n
2)呢？對于長度為L的字符串的最少切割次數等于L-1的切割次數+1或者如果最后一個字符能夠跟前面的子字符串構成回文的話，就等于去除該子串的剩余部分的切割次數+1。
有些拗口，還是看狀態轉移公式吧：
minCut(j)= min(
minCut(j-i-1)+1: if s(i,j) is palindrom
where 0<=i<j ,
minCut(j-1)+1) |
同時優化一下回文的判斷，減少函數調用。
private boolean isPalindrome(char[] ch, int i,int j){
while(i<j){
if(ch[i]!=ch[j]){
return false;
}
++i;
--j;
}
return true;
}
public int minCut(String s){
int totalLength = s.length();
int[] M = new int[totalLength];
char[] ch = s.toCharArray();
M[0]=0;
for(int i=1;i<totalLength;++i){
int min = 99999;
for(int j=0;j<=i;++j){
int cut = 99999;
if(isPalindrome(ch,j,i)){
if(j>0){
cut = M[j-1]+1;
}
else{
cut = 0;
}
if(min>cut){
min = cut;
}
}
}
M[i]=min;
}
return M[totalLength-1];
}
優化后的結果，大概只需要200ms左右了。