1143. Longest Common Subsequence
MediumLeetCodeGiven 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 <= 1000
text1
andtext2
consist of only lowercase English characters.
How to solve the problem
- Recursion with Memoization
# Approach 1: Recursion with Memoization
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n = len(text1)
m = len(text2)
@cache
def dfs(i, j):
# Base case: empty string, LCS is 0.
if i < 0 or j < 0:
return 0
# If characters match, include them in LCS.
if text1[i] == text2[j]:
return dfs(i - 1, j - 1) + 1
# If characters don't match, take max of excluding one char.
return max(dfs(i - 1, j), dfs(i, j - 1))
# Start from the end of both strings.
return dfs(n - 1, m - 1)
- Optimized Dynamic Programming
# Approach 2: Optimized Dynamic Programming
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# DP array: f[j] stores LCS length for text1 (current char) and text2[:j].
f = [0] * (len(text2) + 1)
# Iterate through each char 'x' in text1.
for x in text1:
# 'pre' holds f[j] from previous iteration (row).
pre = 0
# Iterate through each char 'y' in text2.
for j, y in enumerate(text2):
# Save f[j+1] before update (for next 'pre').
tmp = f[j + 1]
# DP transition: if chars match, add 1 to diagonal (pre);
# else, take max of skipping x (f[j+1]) or skipping y (f[j]).
f[j + 1] = pre + 1 if x == y else max(f[j + 1], f[j])
# Update 'pre' for next iteration.
pre = tmp
# f[-1] contains the final LCS length.
return f[-1]
Complexity
- Approach 1 (Recursion with Memoization): Time complexity: O(n * m), Space complexity: O(n * m)
- Approach 2 (Optimized DP): Time complexity: O(n * m), Space complexity: O(m)
Comments
No comments yet. Be the first to comment!