LeetCode/JavaScript/interleaving-string.js at main · PranamBhat/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */

var isInterleave = function(s1, s2, s3) {

    var dp = {};
    if (s3.length !== s1.length + s2.length)
        return false;

    return helper(s1, s2, s3, 0, 0, 0, dp);
};

var helper = function (s1, s2, s3, i, j, k, dp) {

    var res = false;

    if (k >= s3.length)
        return true;

    if (dp['' + i + j + k] !== undefined)
        return dp['' + i + j + k];

    if (s3[k] === s1[i] && s3[k] === s2[j]) {
        res = helper(s1, s2, s3, i + 1, j, k + 1, dp) || helper(s1, s2, s3, i, j + 1, k + 1, dp);
    }
    else if (s3[k] === s1[i]) {
        res = helper(s1, s2, s3, i + 1, j, k + 1, dp);
    }
    else if (s3[k] === s2[j]) {
        res = helper(s1, s2, s3, i, j + 1, k + 1, dp);
    }

    dp['' + i + j + k] = res;

    return res;

};