Longest Common Subsequence
Medium · dynamic programming
A subsequence of a string is what you get by deleting zero or more characters without changing the order of the rest. For example, "ace" is a subsequence of "abcde", but "aec" is not.
Given two strings text1 and text2, return the length of their longest common subsequence, the longest string that is a subsequence of both.
If the two strings share no characters, return 0.
Examples
Example 1
Input: text1 = "abcde", text2 = "ace"
Output: 3
The subsequence "ace" appears in both strings, and no common subsequence is longer.
Example 2
Input: text1 = "abc", text2 = "abc"
Output: 3
Identical strings share all of their characters.
Example 3
Input: text1 = "abc", text2 = "def"
Output: 0
No character is shared, so the answer is 0.
Constraints
- 1 <= len(text1), len(text2) <= 1000
- Both strings contain only lowercase English letters.