小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

回文字符串的切割问题

Posted on 2013-04-11 11:24 小明 阅读(4122) 评论(3)  编辑  收藏 所属分类: 数据结构和算法

问题给定一个字符串s,分割s使得每个子串都是回文的(即倒过来和原字符串是一样的,如aba)
求最少的分割次数。

比如对于“aaba”返回1.(分割方法:["a","aba"])

public class Solution {
    public int minCut(String s) {
       //write your code here
    }
}

解法一:【递归】
对于一个字符串,先找到第一段回文子字符串,然后再求余下的子串的最少分割数,然后再加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(n3)的复杂度,使用了三层循环。对于上面的字符串大概需要花4000ms左右的时间。

有没有办法把复杂度降为O(n2)呢?对于长度为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左右了。

评论

# re: 回文字符串的切割问题[未登录]  回复  更多评论   

2013-04-17 12:39 by Harry
object Palindrome {
def isPelindrome(l:String):Boolean = {
val fhalf = l.take(l.length/2)
val shalf = l.takeRight(l.length/2).reverse
if (fhalf==shalf) true else false
}
def minCut(s:String,partition:Int):Int = {
val ss = s.take(partition)
val ts = s.takeRight(s.length - partition)
if (isPelindrome(ss)&&isPelindrome(ts)) 1 else 0
}
def main(args: Array[String]): Unit = {
val stime = System.currentTimeMillis()
val t = {for (i <- 1 to 14000) yield "a"}.foldLeft(""){case (c,s)=> s+c}
val r = for (i <- 1 to t.size) yield minCut(t,i)
println(r.sum)
println(System.currentTimeMillis() - stime)
}

}

result: 14,000 "a", takes 2669 ms

# re: 回文字符串的切割问题  回复  更多评论   

2013-10-13 22:07 by selldogs
第三个的复杂度也是 O(N^3) , 你每次判断是否是回文 不是也有一个O(N)的循环么

# re: 回文字符串的切割问题  回复  更多评论   

2014-05-22 14:12 by 2dog
@selldogs
同意
这算法本身就是O(n^3)的

只有注册用户登录后才能发表评论。


网站导航: