Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

Strategy #

• We identify that with two texts we need two indexes to write the recurrance
• We compare the strings at each index.
• On match -> we move both index by 1 (i-1, j-1)
• On not match, we pick/not pick the next indexes (i-1, j) (i, j-1)

Patterns #

• Dynamic Programming on string
• Pick/not pick and then we optimize

Code #

const lcsMemo = (text1, text2) => {
  let memo = Array(text1.length)
    .fill(-1)
    .map(() => Array(text2.length).fill(-1));

  function helper(idx1, idx2, memo) {
    // base case
    if (idx1 < 0 || idx2 < 0) return 0;
    if (memo[idx1][idx2] !== -1) return memo[idx1][idx2];

    if (text1[idx1] === text2[idx2]) {
      memo[idx1][idx2] = 1 + helper(idx1 - 1, idx2 - 1, memo);
      return memo[idx1][idx2];
    } else {
      memo[idx1][idx2] = Math.max(
        helper(idx1 - 1, idx2, memo),
        helper(idx1, idx2 - 1, memo)
      );
      return memo[idx1][idx2];
    }
  }

  return helper(text1.length - 1, text2.length - 1, memo);
};

const lcsTabulation = (text1, text2) => {
  const m = text1.length;
  const n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
};

Big-O #

• Recursion - O (N^2 * M^2)
• Memo - O(NxM) time, space O(NxM) O(N+M) Auxillary Stack Space
• Tab - O(NxM) time, space O(NxM)
• Space Optimized - O(NxM) time, space O(N)

Video #