0097. 交错字符串.md

97. 交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

code

动态规划，dp[i][j]表示s1[:i]+s2[:j]能否组成s3[:i+j]。 dp[i][j] = 1有两种情况：

1. s3的第i+j个字符与s1的第i个字符相同，并且s3的前i+j-1个字符可以由s1的前i-1和s2的前j个字符组成；
2. s3的第i+j个字符与s2的第j个字符相同，并且s3的前i+j-1个字符可以由s1的前i和s2的前j-1个字符组成.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        if(len1 + len2 != len3)
            return false;
        vector<vector<int> > dp(len1+1, vector<int>(len2+1, 0));
        dp[0][0] = 1; //dp[0][0]没有意义，设置为1.
        for(int i=1; i<=len1; i++){
            dp[i][0] = s1[i-1] == s3[i-1] && dp[i-1][0];
        }
        for(int j=1; j<=len2; j++){
            dp[0][j] = s2[j-1] == s3[j-1] && dp[0][j-1];
        }
        for(int i=1; i<=len1; i++){
            for(int j=1; j<=len2; j++){
                if(s3[i+j-1] == s1[i-1] && dp[i-1][j] || s3[i+j-1] == s2[j-1] && dp[i][j-1])
                    dp[i][j] = 1;
            }
        }
        return dp[len1][len2];
    }
};