Posted on 2013-04-11 11:24
小明 阅读(4136)
评论(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左右了。