A subsequence of a string keeps some of its characters, in their original order, and drops the
rest: ace is a subsequence of abcde, but aec is not.
Given two strings text1 and text2, return the length of the longest string that is a
subsequence of both. If they share no character, return 0.
Example 1
- Input
- text1 = "stone", text2 = "longest"
- Output
- 3
one appears, in order, in both.Example 2
- Input
- text1 = "abc", text2 = "def"
- Output
- 0
Constraints
text1andtext2each hold 1 to 1000 lowercase letters.
Show the pattern
Dynamic programming (2D)
Two strings, and the answer for a pair of prefixes comes from the answers for slightly shorter pairs: a 2D table indexed by a position in each string.
See dynamic programming (2d) in a visualiserShow the approach
Let L[i][j] be the length of the longest common subsequence of the first i characters of
text1 and the first j characters of text2. An empty prefix shares nothing, so the first row
and column are 0.
Look at the last characters of the two prefixes. If they are equal, a longest common subsequence
can end with that character, so L[i][j] = L[i − 1][j − 1] + 1. If not, at least one of them
isn't used, so L[i][j] is the larger of L[i − 1][j] (drop the last of text1) and
L[i][j − 1] (drop the last of text2).
Fill the table row by row; each row reads only the one above, so two rows are enough. The answer is the bottom-right entry.
Time: O(m × n) · Space: O(n)