Longest Common Subsequence
Problem
Given two strings, return the length of the longest sequence of characters that appears in both, in the same relative order but not necessarily contiguously. Return 0 if they share nothing.
Examples
Constraints
- • 1 <= text1.length, text2.length <= 1000
- • Only lowercase English letters
Hints & approach
Hint 1
Compare the last characters of the two prefixes.
Hint 2
If they match, they can both be part of the answer.
Hint 3
dp[i][j] = a[i-1] == b[j-1] ? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]).
Approachtry the hints first
Let dp[i][j] be the LCS length of the first i characters of text1 and the first j of text2. Row 0 and column 0 are 0 because an empty string shares nothing. If the current characters match, extend the diagonal by 1; otherwise drop one character from either string and take the better result. Fill the table row by row; keeping just two rows reduces space to O(min(m, n)).
Time O(m·n) · Space O(min(m, n))