Problem
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
- For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.
Algorithm
Dynamic Programming (DP). Define state f(i, j) is the common subsequence of text1[0…i] and text2[0…j], so we have
f
(
i
,
j
)
=
{
f
(
i
−
1
,
j
−
1
)
+
1
if
s
[
l
e
f
t
]
=
=
s
[
r
i
g
h
t
]
max
[
f
(
i
−
1
,
j
)
,
f
(
i
,
j
−
1
)
]
otherwise
f(i, j) = \begin{cases} f(i-1, j-1) + 1 & \text{if } s[left] == s[right ]\\ \max[f(i-1, j), f(i, j-1)] & \text{otherwise} \end{cases}
f(i,j)={f(i−1,j−1)+1max[f(i−1,j),f(i,j−1)]if s[left]==s[right]otherwise
Code
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
slen1 = len(text1)
slen2 = len(text2)
if not slen1 or not slen2:
return 0
dp = [[0] * (slen2 + 1) for i in range(slen1 + 1)]
for i in range(1, slen1 + 1):
for j in range(1, slen2 + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[slen1][slen2]