LeetCode: Longest Common Subsequence Solution

Classic dynamic programming problem

Approach: Memoized Recursion

Let recursion(m, n) return length of the longest common subsequence of text1.substring(0, m) and text2.substring(0, n). m and n here refer to length, not 0-based index

if m === 0 || n === 0, recursion(m, n) returns 0
if text[m - 1] === text[n - 1], recursion(m, n) returns 1 + recursion(m - 1, n - 1)
else recursion(m, n) returns max(recursion(m, n - 1), recursion(m - 1, n))

Implementation

1var longestCommonSubsequence = function (text1, text2) {
2  const memo = Array.from({ length: text1.length + 1 }, _ =>
3    Array(text2.length + 1).fill(null)
4  )
5
6  const recursion = (m, n) => {
7    if (memo[m][n] !== null) return memo[m][n]
8
9    if (m === 0 || n === 0) return (memo[m][n] = 0)
10
11    if (text1[m - 1] === text2[n - 1])
12      return (memo[m][n] = 1 + recursion(m - 1, n - 1))
13
14    return (memo[m][n] = Math.max(recursion(m, n - 1), recursion(m - 1, n)))
15  }
16
17  return recursion(text1.length, text2.length)
18}