97. Interleaving String

97. Interleaving String

因为如果可以实现交替，就必然满足|n - m| <= 1这个条件，所以这个条件可以不用考虑

dp:

1. 递归
2. 带memory的递归top-down
3. bottom-up

递归

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

但是在递归过程中，如果有些部分有几个重复的连续串，那么就会产生运算的交叠，所以使用memo来规避已经计算过的内容

sample:

top-down

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        dp = vector<vector<int>>(s1.size(), vector<int>(s2.size(), - 1));
        if(s1.size() + s2.size() != s3.size())
            return false;
        return helper(s1, s2, s3, 0, 0, 0);
    }
private:
    vector<vector<int>> dp;
    bool helper(string& s1, string& s2, string& s3, int i, int j, int k)
    {
        if(i >= s1.size())
            return isEquel(s2, s3, j, k);
        if(j >= s2.size())
            return isEquel(s1, s3, i, k);
        if(dp[i][j] >= 0)
            return dp[i][j] == 1;
        bool ans = false;
        if((s1[i] == s3[k] && helper(s1, s2, s3, i + 1, j, k + 1)) || (s2[j] == s3[k] && helper(s1, s2, s3, i, j + 1, k + 1)))
            ans = true;
        dp[i][j] = ans ? 1 : 0;
        return ans;
    }
    bool isEquel(string& s1, string& s2, int i, int j)
    {
        if(s1.size() - i != s2.size() - j)
            return false;
        while(i < s1.size())
        {
            if(s1[i++] != s2[j++])
                return false;
        }
        return true;
    }
};

bottom-up

dp[i][j]表示(0..i)的s1子串和(0..j)的s2子串，如果他们可以交错成一个(0...i+j+1)的s3子串，那么就是true

2种情况

1. 当s1[i]!=s3[i+j+1] && s2[j]!=s3[i+j+1]，那么绝对为false，因为某尾匹配不了
2. 当s1[i]==s3[i+j+1]时，那么结果等同于dp[i-1][j]，最后一位把s1[i]匹配走了，那么如果之前都匹配成功，就是true了，当s2[j]==s3[i+j+1]时同理

base:
当一个子串为空串时候的匹配结果

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

            }
        }
        return dp.back().back();
    }
};

优化空间

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

            }
        }
        return dp.back();
    }
};

review

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