HardPro challengePython
Dynamic Programming — Longest Common Subsequence
PythonDynamic ProgrammingStrings
Given two strings s1 and s2, return the length of their longest common subsequence (LCS).
A subsequence is formed by deleting some characters without changing the order.
Examples
solve("abcde", "ace")→3("ace")solve("abc", "abc")→3solve("abc", "def")→0
Constraints
- Use bottom-up 2-D DP table.
0 ≤ len(s1), len(s2) ≤ 1000.
Sample tests
Test #1LCS is "ace"
Input: ["abcde","ace"]
Output: 3
Test #2Identical strings
Input: ["abc","abc"]
Output: 3
Test #3No common chars
Input: ["abc","def"]
Output: 0