Longest Common Subsequence
Problem Description
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.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Constraints:
1 <= text1.length, text2.length <= 1000text1andtext2consist of only lowercase English characters.
Solve it on LeetCode
Approaches
1. Recursion
Intuition:
The simplest way to solve this problem is to use recursion. For each character in the two strings, we have two choices:
- If the current characters in both strings are the same, consider the character as part of the subsequence and move to the next character in both strings.
- If the characters do not match, independently consider the two possibilities:
- Exclude the current character of the first string and include the possibility of the rest.
- Exclude the current character of the second string and include the possibility of the rest.
The maximum of these choices will give us the length of the longest common subsequence.
Code:
- Time Complexity: O(2^{min(m, n)})) due to exponential number of subproblems where (m) and (n) are the lengths of the two strings.
- Space Complexity: O(m + n) considering the call stack space.
2. Recursion with Memoization (Top-Down DP)
Intuition:
Recursion leads to overlapping subproblems. By storing and reusing already computed results, we can reduce unnecessary computations. We use a 2D array (memoization table) to store the lengths of the longest common subsequence for substrings seen so far.
Code:
- Time Complexity: O(m * n)
- Space Complexity: O(m * n), due to memoization table.
3. Dynamic Programming (Bottom-Up DP)
Intuition:
Instead of solving the problem recursively, use an iterative approach by filling up a DP table where dp[i][j] represents the length of the longest common subsequence of text1[0:i-1] and text2[0:j-1].
- Initialize a table with dimensions ((m+1) \times (n+1)) to zero.
- Fill the table iteratively based on character match:
- If characters match,
dp[i][j] = 1 + dp[i-1][j-1]. - Otherwise,
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]).
Code:
- Time Complexity: O(m * n)
- Space Complexity: O(m * n) though it can be improved to O(min(m, n)) by using a 1D array if desired.