Leetcode - Longest Common Subsequence

Question

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Idea

• Pretty much just like Leetcode - Unique Paths
• Use recursive dp with 2 indices, tracking the position in each string
• We want to return 0 if we are out of bounds because that means we don’t have a letter to add to our subsequence
• If our letters are the same we can add to our subsequence so we return 1
• If our letters are not the same, we want to increment i and j independently and return the max of the two recursive calls
• We can memoize our i, j position results here for a more efficient solution

Solution