Longest Common Subsequence
Given two strings, find the length of their longest common subsequence (LCS).
A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. For example, "ace" is a subsequence of "abcde" because we can delete "b" and "d". But "aec" is not, because the order changes. A common subsequence is a string that is a subsequence of both inputs.
Input & Output
Input
word1 — the first string
word2 — the second string
Output
the length of the longest string that is a subsequence of both word1 and word2
Example
Input
word1 = "abcde", word2 = "ace"
Output
3
Explanation
Deleting "b" and "d" from "abcde" leaves "ace", which is all of word2, so the longest common subsequence has length 3.
Example
Input
word1 = "abcd", word2 = "dcba"
Output
1
Explanation
The two strings share all four characters, but reversing the order means no two of them appear in the same relative order in both strings. Any single character, such as "a", is a common subsequence, so the answer is 1.
Constraints
1 <= word1.length, word2.length <= 1000word1andword2consist of lowercase English characters