Longest Common Subsequence
Problem Statement
Given two strings text1
and text2
, return the length of the longest common subsequence between the two strings if one exists, otherwise return 0
.
A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.
- For example,
"cat"
is a subsequence of"crabt"
.
A common subsequence of two strings is a subsequence that exists in both strings.
Example 1:
Input: text1 = "cat", text2 = "crabt"
Output: 3
Explanation: The longest common subsequence is “cat” which has a length of 3.
Example 2:
Input: text1 = "abcd", text2 = "abcd"
Output: 4
Example 3:
Input: text1 = "abcd", text2 = "efgh"
Output: 0
Constraints:
1 <= text1.length, text2.length <= 1000
text1
andtext2
consist of only lowercase English characters.
Recommended Time and Space Complexity
Aim for O(m*n)
time and O(min(m, n))
space, where m
and n
are the lengths of the input strings.
Hint 1
Consider using dynamic programming.
Hint 2
Create a 2D array to store lengths of common subsequences of prefixes of the two strings.
Hint 3
The value at dp[i][j]
represents the length of the longest common subsequence of text1[0...i-1]
and text2[0...j-1]
.
Solution
Recursion
def longest_common_subsequence(text1: str, text2: str) -> int: def dfs(i, j): if i == len(text1) or j == len(text2): return 0 if text1[i] == text2[j]: return 1 + dfs(i + 1, j + 1) return max(dfs(i + 1, j), dfs(i, j + 1))
return dfs(0, 0)
Time complexity: O(2 ^ {m + n})
Space complexity: O(m + n)
Where
m
is the length of the stringtext1
andn
is the length of the stringtext2
.