Solution: Longest Common Subsequence
Explore the longest common subsequence problem by applying top-down dynamic programming with memoization. Understand how to optimize the naive recursive approach through a 2D lookup table that stores intermediate results. This lesson helps you grasp the time and space complexity improvements achieved by caching subproblem solutions, enabling efficient comparison of two strings to find their longest subsequence.
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