Solution: Longest Common Subsequence
Explore solving the longest common subsequence problem by applying a dynamic programming approach. Understand how memoization reduces time complexity and learn to implement a 2D table solution for comparing two strings efficiently.
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