Interleaving String

Given s1, s2, s3, 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.

//方案一，递归，超时。复杂度o(n+m)
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        //base condition
        if(s1.empty() && s2.empty() && s3.empty()){
            return true;
        }
        else if(s1.empty() || s2.empty() || s3.empty()){
            return false;
        }
        else{
            bool state;
            if(s3[0] == s1[0]){
                state = isInterleave(s1.substr(1, -1), s2, s3.substr(1, -1));
                if(state == true){
                    return true;
                }
            }
            if(s3[0] == s2[0]){
                state = isInterleave(s1, s2.substr(1, -1), s3.substr(1, -1));
                if(state == true){
                    return true;
                }
            }
            return false;
        }
    }
};

将递归改成了循环，依旧超时。

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        stack<size_t> st1;
        stack<size_t> st2;
        stack<size_t> st3;
        size_t i = 0;
        size_t j = 0;
        size_t k = 0;
        while(i < s1.size() && j < s2.size() && k < s3.size()){
            if(s3[k] == s1[i] && s3[k] == s2[j]){
                //move s2 and s3 then push the state into stack
                st1.push(i);
                st2.push(j + 1);
                st3.push(k + 1);
            }
            if(s3[k] == s1[i]){
                k++;
                i++;
            }
            else if(s3[k] == s2[j]){
                k++;
                j++;
            }
            else if(st1.empty() == false){
                i = st1.top();
                j = st2.top();
                k = st3.top();
                st1.pop();
                st2.pop();
                st3.pop();
            }
            else{
                return false;
            }
        }
        return true;
    }
};

参考了这篇博客http://my.oschina.net/zuoyc/blog/347676，当递归超时时，应该考虑动态规划。

//dp[i][j]表示用s1的前i个字符和s2的前j个字符能否interleave组成s3的前j+i个字符。
//dp[i][j] = (dp[i-1][j] && s1[i - 1] == s3[i + j - 1]) ||(dp[i][j-1] && s2[j - 1] == s3[i + j - 1])
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.size() + s2.size() != s3.size()) return  false;
        bool dp[s1.size() + 1][s2.size() + 1];
        memset(dp, false, sizeof(bool) * (s1.size() + 1) * (s2.size() + 1));
        dp[0][0] = true;
        for(size_t i = 1; i < s1.size() + 1; i++){
            if(s1[i - 1] == s3[i - 1]){
                dp[i][0] = true;    
            }
            else{
                break;
            }
        }
        for(size_t j = 1; j < s2.size() + 1; j++){
            if(s2[j - 1] == s3[j - 1]){
                dp[0][j] = true;
            }
            else{
                break;
            }
        }
        for(size_t i = 1; i < s1.size() + 1; i++){
            for(size_t j = 1; j < s2.size() + 1; j++){
                dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
            }
        }
        return dp[s1.size()][s2.size()];
    }
};