CodeWars: Longest Common Subsequence (Performance Version) Solution

1var recursion = function (text1, text2, i, j, memo) {
2  if (memo[i][j] !== null) {
3    return memo[i][j]
4  }
5
6  if (i === 0 || j === 0) {
7    memo[i][j] = ""
8  } else if (text1[i - 1] === text2[j - 1]) {
9    memo[i][j] = text1[i - 1] + recursion(text1, text2, i - 1, j - 1, memo)
10  } else {
11    let [one, two] = [
12      recursion(text1, text2, i, j - 1, memo),
13      recursion(text1, text2, i - 1, j, memo),
14    ]
15    if (one.length > two.length) {
16      memo[i][j] = one
17    } else {
18      memo[i][j] = two
19    }
20  }
21
22  return memo[i][j]
23}
24
25function lcs(x, y) {
26  let memo = Array.from({ length: x.length + 1 }, (_, i) =>
27    Array(y.length + 1).fill(null)
28  )
29  const res = recursion(x, y, x.length, y.length, memo)
30  return res.split("").reverse().join("")
31}