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}

References

Original problem

Comments

Loading comments...

Tags

leetcode

recursion

dynamic programming

Next Post

CodeWars: Remove Zeroes

Feb 9, 2021

Previous Post

HoningJS

Search Posts