97. Interleaving String

problem description

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

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

algorithm thought

字符串问题，这题其实和最长公共子串问题很像，使用二维数组保存结果，动态规划解决问题。

状态转移方程得出：对于aabcc和dbbca匹配aadbbcbcac问题。我们只需要找到 c==c?以及aabc和dbbca是否匹配aadbbcbca，或者是a==c?以及aabcc和dbbc是否匹配aadbbcbca。上面两中情况任何一种成立，这里的匹配都可以算成功。所以这里动态规划保存之前的结果，这次匹配使用前面的结果解决问题。

code

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.size()+s2.size()!=s3.size())
            return false;
        vector<vector<bool>> pos(s1.size()+1,vector<bool> (s2.size()+1,false));
        pos[0][0]=1;
        for(int i=1;i<=s1.size();++i)
            if(pos[i-1][0]&&s1[i-1]==s3[i-1])
                pos[i][0]=1;
        for(int i=1;i<=s2.size();++i)
            if(pos[0][i-1]&&s2[i-1]==s3[i-1])
                pos[0][i]=1;
        for(int i=1;i<=s1.size();++i)
            for(int j=1;j<=s2.size();++j){
                if((pos[i-1][j]&&s1[i-1]==s3[i+j-1])||(pos[i][j-1]&&s2[j-1]==s3[i+j-1]))
                    pos[i][j]=1;
            }
        return pos[s1.size()][s2.size()];
    }
};

algorithm analysis

设是s1长m，s2长n，会遍历一个m*n的二维数组,最后时间复杂度O(m*n)