小明思考

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

交叉字符串

Posted on 2013-05-10 20:47 小明 阅读(3219) 评论(4)  编辑  收藏 所属分类: 数据结构和算法
问题给定字符串s1,s2,s3,判断s3是否可以由s1和s2交叉组成得到。

例如:

s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.


解法一:(递归)

一个简单的想法,是遍历s3的每个字符,这个字符必须等于s1和s2的某个字符。如果都不相等,则返回false
我们使用3个变量i,j,k分别记录当前s1,s2,s3的字符位置。
如果s3[k] = s1[i], i向后移动一位。如果s3[k]=s2[j],j向后移动一位。
这个题目主要难在如果s1和s2的字符出现重复的时候,就有两种情况,i,j都可以向后一位。
下面的算法在这种情况使用了递归,很简单的做法。但是效率非常差,是指数复杂度的。

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
        
        if(l1+l2!=l3){
            return false;
        }
        
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        
        int i=0,j=0;
        for(int k=0;k<l3;++k){
            char c = c3[k];
            boolean m1 = i<l1 && c==c1[i];
            boolean m2 = j<l2 && c==c2[j];
            if(!m1 && !m2){
                return false;
            }
            else if(m1 && m2){
                String news3 =  s3.substring(k+1);
                return isInterleave(s1.substring(i+1),s2.substring(j),news3)
                                || isInterleave(s1.substring(i),s2.substring(j+1),news3);
            }
            else if(m1){
                ++i;
            }
            else{
                ++j;
            }
        }
        
        return true;        
    }
}


解法二:(动态规划)
为了减少重复计算,就要使用动态规划来记录中间结果。

这里我使用了一个二维数组result[i][j]来表示s1的前i个字符和s2的前j个字符是否能和s3的前i+j个字符匹配。

状态转移方程如下:
result[i,j] = (result[i-1,j] && s1[i] = s3[i+j])  || (result[i,j-1] && s2[j] = s3[i+j]);
其中0≤i≤len(s1) ,0≤j≤len(s2)

这样算法复杂度就会下降到O(l1*l2)
public class Solution {
   
public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
       
        if(l1+l2!=l3){
            return false;
        }
        
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        
        boolean[][] result = new boolean[l1+1][l2+1];
        result[0][0] = true;
        
        for(int i=0;i<l1;++i){
            if(c1[i]==c3[i]){
                result[i+1][0] = true;
            }
            else{
                break;
            }
        }
        
        for(int j=0;j<l2;++j){
            if(c2[j]==c3[j]){
                result[0][j+1] = true;
            }
            else{
                break;
            }
        }
        
        
        for(int i=1;i<=l1;++i){
            char ci = c1[i-1];
            for(int j=1;j<=l2;++j){
                char cj = c2[j-1];
                char ck = c3[i+j-1];
                   result[i][j] = (result[i][j-1] && cj==ck) || (result[i-1][j] && ci==ck);
            }
        }
        
        return result[l1][l2];
   }
}

评论

# re: 交叉字符串  回复  更多评论   

2013-05-11 10:19 by 开发吧
今天正在搞这个问题,谢谢啦!

# re: 交叉字符串  回复  更多评论   

2013-05-12 21:09 by tb
算法 对我有点启发 谢谢

# re: 交叉字符串  回复  更多评论   

2013-05-13 11:23 by javanewer
boolean[][] result = new boolean[l1+1][l2+1];
这一句什么作用?

# re: 交叉字符串[未登录]  回复  更多评论   

2013-05-15 18:57 by wang
交叉字符串是用来干嘛的

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


网站导航: