97.交错字符串（困难）

原题

https://leetcode-cn.com/problems/interleaving-string/

解题思路

动态规划，dp[i][j] 表示 s1.substring(0, i) 和 s2.substring(0, j) 能交错组成 s3.substring(0, i+j)

• dp[0][0] = true
• 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]);

代码

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    const m = s1.length + 1, n = s2.length + 1;
    if (s3.length !== m + n - 2) return false;
    const dp = [];
    for  (let i = 0; i < m; ++i) {
        const temp = new Array(n);
        dp.push(temp);
    }
    dp[0][0] = true;
    for (let i = 1; i < m; ++i) {
        dp[i][0] = dp[i-1][0] && s1[i-1] === s3[i-1];
    }
    for (let j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j-1] && s2[j-1] === s3[j-1];
    }
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            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]);
        }
    }
    return dp[m-1][n-1];
};

复杂度

• 时间复杂度 O(M*N)
• 空间复杂度 O(M*N)