题目描述

给定三个字符串 s1, s2, s3，判断 s3 是否可以由 s1 和 s2 交错而成。

样例1

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

样例2

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

算法

(动态规划) $O(n^2)$

状态表示：$f[i][j]$ 表示 s1 的前 $i$ 个字符和 s2 的前 $j$ 个字符是否可以交错组成 s3 的前 $i + j$ 个字符。
状态转移：如果 $s3[i + j]$ 匹配 $s1[i]$，则问题就转化成了 $f[i - 1][j]$；如果 $s3[i + j]$ 匹配 $s2[j]$，则问题就转化成了 $f[i][j - 1]$。两种情况只要有一种为真，则 $f[i][j]$ 就为真。

时间复杂度分析：状态总共有 $n^2$ 个，状态转移复杂度是 $O(1)$。所以总时间复杂度是 $O(n^2)$。

C++ 代码

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

        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
        for (int i = 0; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
                if (!i && !j) f[i][j] = true;
                else {
                    if (i && s1[i] == s3[i + j]) f[i][j] = f[i - 1][j];
                    if (j && s2[j] == s3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
                }

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