MediumBlind75StringDP
Longest Common Subsequence
Given two strings text1 and text2, return the length of their longest common subsequence.
Examples
Input
text1 = 'abcde', text2 = 'ace'
Output
3
The longest common subsequence is 'ace' with length 3.
Input
text1 = 'abc', text2 = 'def'
Output
0
There is no common subsequence.
Constraints
- •
1 <= text1.length, text2.length <= 1000 - •
text1 and text2 consist of only lowercase English characters.
Approaches
Recursively compare characters and try all possibilities.
CodeT: O(2^(m+n)) | S: O(m+n)
def longest_common_subsequence(text1, text2):
def helper(i, j):
if i == len(text1) or j == len(text2):
return 0
if text1[i] == text2[j]:
return 1 + helper(i + 1, j + 1)
return max(helper(i + 1, j), helper(i, j + 1))
return helper(0, 0)Use a 2D DP table where dp[i][j] is LCS of text1[:i] and text2[:j].
CodeT: O(m * n) | S: O(m * n)
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]Use a 1D array to optimize space.
Diagram
text1 = 'abcde', text2 = 'ace'
dp table:
'' a c e
'' 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3
Result: 3
CodeT: O(m * n) | S: O(min(m, n))
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
if m < n:
text1, text2 = text2, text1
m, n = n, m
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
return prev[n]Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^(m+n)) | O(m+n) | Recursively compare characters and try all possibilities. |
| DP - 2D Table | O(m * n) | O(m * n) | Use a 2D DP table where dp[i][j] is LCS of text1[:i] and text2[:j]. |
| Space Optimized DP | O(m * n) | O(min(m, n)) | Use a 1D array to optimize space. |
Recursion
T: O(2^(m+n))S: O(m+n)
Recursively compare characters and try all possibilities.
DP - 2D Table
T: O(m * n)S: O(m * n)
Use a 2D DP table where dp[i][j] is LCS of text1[:i] and text2[:j].
Space Optimized DP
T: O(m * n)S: O(min(m, n))
Use a 1D array to optimize space.
Common Mistakes
Confusing subsequence with substring
Not initializing the DP table boundaries correctly
Using O(m*n) space when O(min(m,n)) is possible