Longest Common Subsequence
MediumDynamic Programming
You are given two strings text1 and text2. Return the length of their longest common subsequence, or 0 if they share no characters.
A subsequence is what remains after deleting zero or more characters from a string without reordering the rest (so "ace" is a subsequence of "abcde", but "aec" is not). A common subsequence appears as a subsequence in both strings.
Example 1
- Input:
- text1 = "stone", text2 = "longest"
- Output:
- 3
- Explanation
oneappears in order in both: s-t-**o**-**n**-**e** and l-**o**-**n**-g-**e**-s-t. No 4-letter subsequence is shared.
Example 2
- Input:
- text1 = "abc", text2 = "cba"
- Output:
- 1
- Explanation
- Any two letters appear in opposite orders in the two strings, so only a single letter can be shared.
Example 3
- Input:
- text1 = "dog", text2 = "cat"
- Output:
- 0
- Explanation
- The strings share no letters at all.
Constraints
- 1 ≤
text1.length,text2.length≤ 1000 text1andtext2consist of lowercase English letters