Find longest common subsequence (LCS) (Memoization)

Given two strings, s1 and s2, find length of the longest common subsequence. Return 0 for nothing common.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find longest common subsequence (LCS), but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = None

def count(s1, s2):
  if len(s1) <= 0 or len(s2) <= 0:
    return 0

  global cache
  if not cache:
    cache = [[None for _ in range(len(s2))] for _ in range(len(s1))]

  if not cache[len(s1) - 1][len(s2) - 1]:
    mx = float('-inf')

    if s1[0] == s2[0]:
      mx = 1 + count(s1[1:], s2[1:])

    cache[len(s1) - 1][len(s2) - 1] = max(mx, count(s1[1:], s2), count(s1, s2[1:]))

  return cache[len(s1) - 1][len(s2) - 1]

s1 = "abc"
s2 = "acd"

print(count(s1, s2))

let cache = null;

function count(s1, s2) {
  if (s1.length <= 0 || s2.length <= 0) {
    return 0;
  }

  if (cache === null) {
    cache = []

    for (let i = 0; i < s1.length; i++) {
      cache[i] = [];
    }
  }

  if (cache[s1.length - 1][s2.length - 1] === undefined) {
    let max = -Infinity;

    if (s1[0] === s2[0]) {
      max = 1 + count(s1.slice(1), s2.slice(1));
    }

    cache[s1.length - 1][s2.length - 1] = Math.max(max, count(s1.slice(1), s2), count(s1, s2.slice(1)));
  }

  return cache[s1.length - 1][s2.length - 1];
}

const s1 = "abc";
const s2 = "acd";

console.log(count(s1, s2));