# 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

Search Posts