Dynamic Programming
LC #1143Medium
Longest Common Subsequence
Dynamic Programming
AmazonGoogleMetaBloombergMicrosoftProblem
Find the length of the longest subsequence common to two strings.
stringdynamic-programming
Constraints
- ›1 ≤ text1.length, text2.length ≤ 1000
- ›Lowercase English letters only
Example
Input
text1 = "abcde", text2 = "ace"Output
3Why
LCS is "ace" (length 3). A subsequence need not be contiguous