blob: 6bd7f0f7a70aa9afc5b1dbe78dba6d6bb7afff47 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
# 1143. Longest Common Subsequence
"""
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 characers (can be none) deleted without changing the relative order
of the remaining characters. a common subsequence of two strings is a
subsequence that is common to both strings.
"""
class Solution(object):
def longestCommonSubsequence(self, text1, text2):
"""
:type text1: str
:type text2: str
:rtype: int
"""
dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
for i, c in enumerate(text1):
for j, d in enumerate(text2):
dp[i + 1][j + 1] = (
1 + dp[i][j] if c == d else max(dp[i][j + 1], dp[i + 1][j])
)
return dp[-1][-1]
if __name__ == "__main__":
obj = Solution()
print(obj.longestCommonSubsequence("abcde", "ace")) # expect: 3
print(obj.longestCommonSubsequence("abc", "abc")) # expect: 3
print(obj.longestCommonSubsequence("abc", "def")) # expect: 0
|