# 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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var 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}```

Original problem

## Tags

leetcode

recursion

dynamic programming

## Next Post

CodeWars: Remove Zeroes

Feb 9, 2021

Search Posts