aboutsummaryrefslogtreecommitdiff
path: root/longest_increasing_subseq2.py
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