Longest Common Subsequence
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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))
