Solution: Longest Common Subsequence
Explore how to find the longest common subsequence between two strings by applying a top-down dynamic programming approach. Understand the concept of memoization to optimize recursive solutions and store intermediate results for efficient lookups. This lesson helps you grasp both the problem constraints and the method to implement an improved algorithm with reduced time complexity.
Statement
Suppose you are given two strings. You need to find the length of the longest common subsequence between these two strings.
A subsequence is a string formed by removing some characters from the original string while maintaining the relative position of the remaining characters. For example, “abd” is a subsequence of “abcd”, where the removed character is “c”.
If there is no common subsequence, then return 0.
Constraints:
-
str1.length