Longest Common Subsequence
Medium
Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence is a sequence that can be formed by deleting some characters from a string without changing the order of the remaining characters.
Example 1
Input
text1 = "abcde" text2 = "ace"
Output
3
Explanation
The longest common subsequence is "ace".
Its length is 3.
Example 2
Input
text1 = "abc" text2 = "abc"
Output
3
Explanation
Both strings are identical, so the entire string is the longest common subsequence.
Constraints
1 <= text1.length
text2.length <= 1000
text1 and text2 consist of lowercase English letters.
Hints:
Hint 1
Define dp[i][j] as the length of the longest common subsequence between the first i characters of text1 and the first j characters of text2.
Hint 2
If the current characters are equal:
dp[i][j] = dp[i-1][j-1] + 1
Otherwise, choose the better result by skipping one character:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Auto
Loading editor...
Input
Expected Output