This is a classic Leetcode dynamic programming problem. The simplest way to think about it is just to look at the 1st characters of the strings and use recursion.

If they're equal then the LCS is just that of the remaining strings - plus 1!

If they're different, then we

take the LCS of the first string and the second without the 1st character
take the LCS of the first string without its 1st character with the second string
the LCS is that of the max of 1 and 2

Then just add memoization..

Or convert to an iterative table form as in Cormen

0 comments

Some drafts from the Git Zine

The Sieve of Eratosthenes (in 1 line of functional Python!)

See all posts from Neal C