Solution: Longest Common Subsequence
Understand how to solve the longest common subsequence problem by exploring both naive recursion and an optimized dynamic programming approach. Learn to use memoization with a 2D table to avoid redundant calculations, improving time complexity from exponential to polynomial. This lesson teaches you the conceptual and practical implementation of dynamic programming to efficiently compute subsequence lengths in two input strings.
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