97. Interleaving String

Problem

Tags: String, Dynamic Programming

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

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

Example 2:

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

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

Code

JS

// 97. Interleaving String (1/10/53391)
// Runtime: 168 ms (2.45%) Memory: 42.42 MB (93.46%) 

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    let m = s1.length, n = s2.length;

    if(m + n !== s3.length) return false;
    
    let dp = [];
    for(let i = 0; i <= m; i++) {
        let row = [];
        for(let j = 0; j <= n; j++) row.push(false);
        dp.push(row);
    }
    
    dp[0][0] = true;
    
    for(let i = 1; i <= m; i++) {
        dp[i][0] = dp[i - 1][0] && s3[i - 1] === s1[i - 1];
    }
    
    for(let j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] && s3[j - 1] === s2[j - 1];
    }
    
    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            dp[i][j] = (dp[i - 1][j] && s3[i - 1 + j] === s1[i - 1]) || (dp[i][j - 1] && s3[j - 1 + i] === s2[j - 1]);
        }
    }
    
    return dp[m][n];
};