0115-distinct-subsequences.js

/**
 * DP - Top Down
 * Matrix - Memoization
 * Time O(N * M) | Space (N * M)
 * https://leetcode.com/problems/distinct-subsequences/
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = (s, t, i = 0, j = 0, memo = initMemo(s, t)) => {
    const isBaseCase1 = s.length < t.length;
    if (isBaseCase1) return 0;

    const isBaseCase2 = j === t.length;
    if (isBaseCase2) return 1;

    const isBaseCase3 = i === s.length;
    if (isBaseCase3) return 0;

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

    return dfs(
        s,
        t,
        i,
        j,
        memo,
    ); /* Time O(N * M) | Space O((N * M) + HEIGHT) */
};

var initMemo = (s, t) =>
    new Array(s.length).fill().map(() => new Array(t.length).fill(null));

var dfs = (s, t, i, j, memo) => {
    const left = numDistinct(
        s,
        t,
        i + 1,
        j,
        memo,
    ); /* Time O(N * M) | Space O(HEIGHT) */

    const isEqual = s[i] === t[j];

    const right = isEqual
        ? numDistinct(
              s,
              t,
              i + 1,
              j + 1,
              memo,
          ) /* Time O(N * M) | Space O(HEIGHT) */
        : 0;

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

/**
 * DP - Bottom Up
 * Matrix - Tabulation
 * Time O(N * M) | Space (N * M)
 * https://leetcode.com/problems/distinct-subsequences/
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = (s, t) => {
    const tabu = initTabu(s, t); /* Time O(N * M) | Space O(N * M) */

    search(s, t, tabu); /* Time O(N * M) | Space O(N * M) */

    return tabu[0][0];
};

var initTabu = (s, t) => {
    const tabu = new Array(s.length + 1)
        .fill() /* Time O(N) | Space O(N) */
        .map(() => new Array(t.length + 1)); /* Time O(M) | Space O(M) */

    tabu[s.length].fill(0); /*           | Space O(N * M) */

    for (let r = 0; r <= s.length; ++r) {
        /* Time O(N) */
        tabu[r][t.length] = 1; /*       | Space O(N * M) */
    }

    return tabu;
};

var search = (s, t, tabu) => {
    for (let r = s.length - 1; 0 <= r; r--) {
        /* Time O(N) */
        for (let c = t.length - 1; 0 <= c; c--) {
            /* Time O(M) */
            const left = tabu[r + 1][c];

            const isEqual = s[r] === t[c];

            const right = isEqual ? tabu[r + 1][c + 1] : 0;

            tabu[r][c] = left + right; /* Space O(N * M) */
        }
    }
};

/**
 * DP - Bottom Up
 * Matrix - Tabulation
 * Time O(N * M) | Space O(M)
 * https://leetcode.com/problems/distinct-subsequences/
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = (s, t) => {
    const tabu = initTabu(t); /* Time O(M) | Space O(M) */

    search(s, t, tabu); /* Time O(N * M) | Space O(M) */

    return tabu[0];
};

var initTabu = (t) => new Array(t.length).fill(0); /* Time O(M) | Space O(M) */

var search = (s, t, tabu) => {
    for (let row = s.length - 1; 0 <= row; row--) {
        /* Time O(N) */
        let prev = 1;

        for (let col = t.length - 1; 0 <= col; col--) {
            /* Time O(M) */
            const curr = tabu[col];

            const isEqual = s[row] === t[col];
            if (isEqual) tabu[col] += prev; /* Space O(M) */

            prev = curr;
        }
    }
};