题目描述

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

样例

示例 1:

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

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

算法1

(动态规划) $O(mn)$

如果$s1$、$s2$的长度之和不等于$s3$的长度，直接可以返回$false$；
状态表示：
$f[i][j]$代表$s1$的前$i$个字符和$s2$的前$j$个字符，是否能够交错组成$s3$的前$i + j$个字符；

状态转移:
这里举例提供一种理解的角度,这题其实可以看作是能否从左上角走到右下角的问题；
如果选择$s1$中的字符串，就向下走，如果选择$s2$中的字符串，就向右走，走过的路径必须正好组成一个$s3$字符串，例如，第一步要选$a$，只有$s1$中有$a$，所以只能向下走，第四步要选$b$，$s1$和$s2$中都有$b$，既可以往右走也可以往下走；
下表中的数字代表在表中走了几步，其实也就是当前拼成的$s3$有多长。

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
  _ d b b c a
_ 0 x x x x x
a 1 x x x x x
a 2 3 4 5 6 x
b x 4 5 x 7 x
c x x 6 7 8 9
c x x x x x 10 

经过如上转化，可以发现，这道题是一个是否可以到达的问题，所以也可以用$BFS$来做哈哈。

时间复杂度

一共$O(mn)$个状态，每次转移需要$O(1)$时间，所以总时间复杂度为$O(mn)$。

参考文献

C++ 代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size(), s = s3.size();
        if (m + n != s) return false;

        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) f[0][j] = f[0][j - 1] && s3[j - 1] == s2[j - 1];
        for (int i = 1; i <= m; ++i) f[i][0] = f[i - 1][0] && s3[i - 1] == s1[i - 1];

        for (int i = 1; i <= m; ++i){
            for (int j = 1; j <= n; ++j){
                if (s3[i + j - 1] == s1[i - 1]) f[i][j] = f[i - 1][j];
                if (s3[i + j - 1] == s2[j - 1]) f[i][j] = f[i][j] || f[i][j - 1];
            }
        }

        return f[m][n];
    }
};

压缩掉一维空间的DP

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size(), s = s3.size();
        if (m + n != s) return false;

        vector<int> f(n + 1);
        f[0] = true;
        for (int j = 1; j <= n; ++j) f[j] = f[j - 1] && s3[j - 1] == s2[j - 1];

        for (int i = 1; i <= m; ++i){
            f[0] = f[0] && s3[i - 1] == s1[i - 1];
            for (int j = 1; j <= n; ++j){
                if (s3[i + j - 1] != s1[i - 1]) f[j] = false;
                if (s3[i + j - 1] == s2[j - 1]) f[j] = f[j] || f[j - 1];
            }
        }

        return f[n];
    }
};