[97] 交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + ... + sn

t = t1 + t2 + ... + tm

|n - m| <= 1

交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

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

输出：true

示例 2：

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

输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""

输出：true

提示：

0 <= s1.length, s2.length <= 100

0 <= s3.length <= 200

s1、s2、和 s3 都由小写英文字母组成

进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

这道题与求最长连续公共子序列的题目类似，只不过这道题是求两个字符串是否能交错组成第三个字符串。

面对双字符串的动态规划问题，通常我们的 dp 数组思路基本上都是，将其中一个字符串作为行，另一个字符串作为列，然后 dp 数组的每个元素表示的是两个字符串的子串是否能交错组成第三个字符串的子串。

于是问题就变成了，思考每个 dp 元素的变化关系。

我们注意到，若 s1 当前字符与 s3 的当前字符相同，且 s3 之前的字符能由 s1 与 s2 交错组成，则 s3 当前的子串也能由 s1 与 s2 交错组成，同理对 s2 也一样。

因此，我们可以得到状态转移方程：

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])

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const l1 = s1.length;
    const l2 = s2.length;
    const l3 = s3.length;

    if (l1 + l2 !== l3) return false;

    // fn(i, j) 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i + j 个字符
    const dp = Array(l1 + 1).fill(0).map(() => Array(l2 + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i <= l1; i++) {
        for (let j = 0; j <= l2; j++) {
            const k = i + j;
            if (i > 0) {
                // 若 s1 当前字符与 s3 的当前字符相同，且 s3 之前的字符能由 s1 与 s2 交错组成，则 s3 当前的子串也能由 s1 与 s2 交错组成
                dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1[i - 1] === s3[k - 1]);
            }
            if (j > 0) {
                // 若 s2 当前字符与 s3 的当前字符相同，且 s3 之前的字符能由 s1 与 s2 交错组成，则 s3 当前的子串也能由 s1 与 s2 交错组成
                dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2[j - 1] === s3[k - 1]);
            }
        }
    }
    return dp[l1][l2];
};