/**
 * Brute Force - DFS
 * Time O(2^(N + M)) | Space O(N + M)
 * https://leetcode.com/problems/interleaving-string/
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
 var isInterleave = (s1, s2, s3, i = 0, j = 0, res = '') => {
    const isBaseCase1 = (s3.length !== (s1.length + s2.length));
    if (isBaseCase1) return false;

    const isBaseCase2 = ((res === s3) && (i == s1.length) && (j == s2.length));
    if (isBaseCase2) return true;

    return dfs(s1, s2, s3, i, j, res);/* Time O(2^(N + M)) | Space O(N + M) */
}

var dfs = (s1, s2, s3, i, j, res, ans = false) => {
    const hasLeft = (i < s1.length);
    if (hasLeft) ans |= isInterleave(s1, s2, s3, (i + 1), j, `${res}${s1[i]}`); /* Time O(2^(N + M)) | Space O(N) */

    const hasRight = (j < s2.length);
    if (hasRight) ans |= isInterleave(s1, s2, s3, i, (j + 1), `${res}${s2[j]}`);/* Time O(2^(N + M)) | Space O(M) */

    return ans;
}

/**
 * DP - Top Down
 * Matrix - Memoization
 * Time O(N * M) | Space O(N * M)
 * https://leetcode.com/problems/interleaving-string/
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = (s1, s2, s3, i = 0, j = 0, k = 0, memo = initMemo(s1, s2)) => {
    const isBaseCase1 = (s3.length !== (s1.length + s2.length));
    if (isBaseCase1) return false;

    const isBaseCase2 = (i === s1.length);
    if (isBaseCase2) return (s2.slice(j) === s3.slice(k));/* Time O(M + K) | Space O(M + K) */

    const isBaseCase3 = (j === s2.length);
    if (isBaseCase3) return (s1.slice(i) === s3.slice(k));/* Time O(N + K) | Space O(N + K) */

    const hasSeen = (memo[i][j] !== null);
    if (hasSeen) return memo[i][j];

    return dfs(s1, s2, s3, i, j, k, memo);/* Time O(N * M) | Space O((N * M) + HEIGHT) */
}

var initMemo = (s1, s2) => new Array(s1.length).fill()/* Time O(N) | Space O(N) */
    .map(() => new Array(s2.length).fill(null));          /* Time O(M) | Space O(M) */

var dfs = (s1, s2, s3, i, j, k, memo) => {
    const left = ((s3[k] === s1[i]) && isInterleave(s1, s2, s3, (i + 1), j, (k + 1), memo)); /* Time O(N) | Space O(HEIGHT) */
    const right = ((s3[k] === s2[j]) && isInterleave(s1, s2, s3, i, (j + 1), (k + 1), memo));/* Time O(M) | Space O(HEIGHT) */

    memo[i][j] = left || right;                                                              /*           | Space O(N * M) */
    return memo[i][j];
}

/**
 * DP - Bottom Up
 * Matrix - Tabulation
 * Time O(N * M) | Space O(N * M)
 * https://leetcode.com/problems/interleaving-string/
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = (s1, s2, s3) => {
    const isBaseCase = (s3.length !== s1.length + s2.length);
    if (isBaseCase) return false;

    const tabu = initTabu(s1, s2);/* Time O(N * M) | Space O(N * M) */

    search(s1, s2, s3, tabu);     /* Time O(N * M) | Space O(N * M) */

    return tabu[s1.length][s2.length];
}

var initTabu = (s1, s2) => new Array((s1.length + 1)).fill()/* Time O(N) | Space O(N) */
    .map(() => new Array((s2.length + 1)).fill(null))           /* Time O(M) | Space O(M) */

var search = (s1, s2, s3, tabu) => {
    const [ rows, cols ] = [ s1.length, s2.length ];

    for (let row = 0; (row <= rows); row++) {/* Time O(N) */
        for (let col = 0; (col <= cols); col++) {/* Time O(M) */
            tabu[row][col] =                         /* Space O(N * M) */
                hasMatch(s1, s2, s3, row, col, tabu);
        }
    }
}

var hasMatch = (s1, s2, s3, i, j, tabu) => {
    const isBaseCase1 = ((i === 0) && (j === 0));
    if (isBaseCase1) return true;

    const isBaseCase2 = (i === 0);
    if (isBaseCase2) return getRight(i, j, s2, s3, tabu);

    const isBaseCase3 = (j === 0);
    if (isBaseCase3) return getLeft(i, j, s1, s3, tabu);

    const left = getLeft(i, j, s1, s3, tabu);
    const right = getRight(i, j, s2, s3, tabu)

    return (left || right);
}

var getLeft = (i, j, s1, s3, tabu) => ((tabu[(i - 1)][j] && s1[(i - 1)]) === s3[((i + j) - 1)]);

var getRight = (i, j, s2, s3, tabu) => ((tabu[i][(j - 1)] && s2[(j - 1)]) === s3[((i + j) - 1)]);

/**
 * DP - Bottom Up
 * Array - Tabulation
 * Time O(N * M) | Space O(M)
 * https://leetcode.com/problems/interleaving-string/
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = (s1, s2, s3) => {
    const isBaseCase = (s3.length !== (s1.length + s2.length));
    if (isBaseCase) return false;

    const tabu = initTabu(s2);/* Time O(M)     | Space O(M) */

    search(s1, s2, s3, tabu); /* Time O(N * M) | Space O(M) */

    return tabu[s2.length];
};

var initTabu = (s2) => new Array((s2.length + 1)).fill(false);/* Time O(M) | Space O(M) */

var search = (s1, s2, s3, tabu) => {
    const [ rows, cols ] = [ s1.length, s2.length ];

    for (let row = 0; (row <= rows); row++) {/* Time O(N)*/
        for (let col = 0; (col <= cols); col++) {/* Time O(M)*/
            tabu[col] =                              /* Space O(M)*/
                hasMatch(s1, s2, s3, row, col, tabu);
        }
    }
}

var hasMatch = (s1, s2, s3, i, j, tabu) => {
    const isBaseCase1 = ((i === 0) && (j === 0));
    if (isBaseCase1) return true;

    const isBaseCase2 = (i === 0);
    if (isBaseCase2) return getRight(i, j, s2, s3, tabu)

    const isBaseCase3 = (j === 0);
    if (isBaseCase3) return getLeft(i, j, s1, s3, tabu);;

    return getLeft(i, j, s1, s3, tabu) || getRight(i, j, s2, s3, tabu);
}

var getLeft = (i, j, s1, s3, tabu) => (tabu[j] && (s1[(i - 1)] === s3[((i + j) - 1)]));

var getRight = (i, j, s2, s3, tabu) => (tabu[(j - 1)] && (s2[(j - 1)] === s3[((i + j) - 1)]));