首页 > 其他 > 详细

Interleaving String

时间:2014-06-03 14:03:24      阅读:324      评论:0      收藏:0      [点我收藏+]

Given s1s2s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

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

bubuko.com,布布扣
class Solution {
private:
    string s1,s2,s3;
    int** able;
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        if(s1.length()+s2.length()!=s3.length()) return false;
        this->s1=s1;
        this->s2=s2;
        this->s3=s3;
        able=new int*[s1.length()+1];
        for(int i=0;i<=s1.length();i++)
        {
            able[i]=new int[s2.length()+1];
            for(int j=0;j<=s2.length();j++)
                able[i][j]=0;
        }
        able[0][0]=1;
        
        return isleave(s1.length(),s2.length());
    }
    bool isleave(int index1,int index2)
    {
        if(able[index1][index2]!=0) return able[index1][index2]==1;
        if(index2>0 && isleave(index1,index2-1) && s3[index1+index2-1]==s2[index2-1])
        {
            able[index1][index2]=1;
            return true;
        }
        if(index1>0 && isleave(index1-1,index2) && s3[index1+index2-1]==s1[index1-1])
        {
            able[index1][index2]=1;
            return true;
        }
        able[index1][index2]=-1;
        return false;
    }
};
bubuko.com,布布扣

 

Interleaving String,布布扣,bubuko.com

Interleaving String

原文:http://www.cnblogs.com/erictanghu/p/3759581.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!