97. Interleaving String

[Tcdian]

97. Interleaving String

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

Example 1

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    const len1 = s1.length;
    const len2 = s2.length;
    if (len1 + len2 !== s3.length) {
        return false;
    }
    const dp = Array.from(new Array(len1 + 1), () => new Array(len2 + 1));
    for (let i = 0; i <= len1; i++) {
        for (let j = 0; j <= len2; j++) {
            if (i === 0 && j === 0) {
                dp[i][j] = true;
            } else if (i === 0) {
                dp[i][j] = dp[i][j - 1] && s2[j - 1] === s3[i + j - 1];
            } else if (j === 0) {
                dp[i][j] = dp[i - 1][j] && s1[i - 1] === s3[i + j - 1];
            } else {
                dp[i][j] = dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]
                    || dp[i - 1][j] && s1[i - 1] === s3[i + j - 1];
            }

        }
    }
    return dp[len1][len2];
};

• TypeScript Solution

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const len1 = s1.length;
    const len2 = s2.length;
    if (len1 + len2 !== s3.length) {
        return false;
    }
    const dp: boolean[][] = Array.from(new Array(len1 + 1), () => new Array(len2 + 1));
    for (let i = 0; i <= len1; i++) {
        for (let j = 0; j <= len2; j++) {
            if (i === 0 && j === 0) {
                dp[i][j] = true;
            } else if (i === 0) {
                dp[i][j] = dp[i][j - 1] && s2[j - 1] === s3[i + j - 1];
            } else if (j === 0) {
                dp[i][j] = dp[i - 1][j] && s1[i - 1] === s3[i + j - 1];
            } else {
                dp[i][j] = dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]
                    || dp[i - 1][j] && s1[i - 1] === s3[i + j - 1];
            }

        }
    }
    return dp[len1][len2];
};