longest_common_subsequence

View Source

 1from functools import cache
 2
 3
 4# @leet start
 5class Solution:
 6    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
 7        """
 8        To solve this question of the longest common subsequence, note that
 9        for both the strings, we have three choices.
10        1. Either string is empty, in which case the LCS is 0.
11        2. The first character of both strings is equal, in which case
12        we return 1 + the LCS of the remaining strings incremented by 1.
13        3. The characters do not match, in which case our LCS is the max of
14        the LCS if we increment either side.
15
16        We add some caching to this to reduce the time complexity from $O(2^m + n)$
17        to $O(m * n)$, with $O(m * n)$ space complexity.
18        """
19
20        @cache
21        def dfs(p1, p2):
22            if not p1 or not p2:
23                return 0
24            if p1[0] == p2[0]:
25                return 1 + dfs(p1[1:], p2[1:])
26            else:
27                return max(dfs(p1, p2[1:]), dfs(p1[1:], p2))
28
29        return dfs(text1, text2)
30
31
32# @leet end
33
34
35def test():
36    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
 8        """
 9        To solve this question of the longest common subsequence, note that
10        for both the strings, we have three choices.
11        1. Either string is empty, in which case the LCS is 0.
12        2. The first character of both strings is equal, in which case
13        we return 1 + the LCS of the remaining strings incremented by 1.
14        3. The characters do not match, in which case our LCS is the max of
15        the LCS if we increment either side.
16
17        We add some caching to this to reduce the time complexity from $O(2^m + n)$
18        to $O(m * n)$, with $O(m * n)$ space complexity.
19        """
20
21        @cache
22        def dfs(p1, p2):
23            if not p1 or not p2:
24                return 0
25            if p1[0] == p2[0]:
26                return 1 + dfs(p1[1:], p2[1:])
27            else:
28                return max(dfs(p1, p2[1:]), dfs(p1[1:], p2))
29
30        return dfs(text1, text2)

def longestCommonSubsequence(self, text1: str, text2: str) -> int: View Source

 7    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
 8        """
 9        To solve this question of the longest common subsequence, note that
10        for both the strings, we have three choices.
11        1. Either string is empty, in which case the LCS is 0.
12        2. The first character of both strings is equal, in which case
13        we return 1 + the LCS of the remaining strings incremented by 1.
14        3. The characters do not match, in which case our LCS is the max of
15        the LCS if we increment either side.
16
17        We add some caching to this to reduce the time complexity from $O(2^m + n)$
18        to $O(m * n)$, with $O(m * n)$ space complexity.
19        """
20
21        @cache
22        def dfs(p1, p2):
23            if not p1 or not p2:
24                return 0
25            if p1[0] == p2[0]:
26                return 1 + dfs(p1[1:], p2[1:])
27            else:
28                return max(dfs(p1, p2[1:]), dfs(p1[1:], p2))
29
30        return dfs(text1, text2)

To solve this question of the longest common subsequence, note that for both the strings, we have three choices.

Either string is empty, in which case the LCS is 0.
The first character of both strings is equal, in which case we return 1 + the LCS of the remaining strings incremented by 1.
The characters do not match, in which case our LCS is the max of the LCS if we increment either side.

We add some caching to this to reduce the time complexity from $O(2^m + n)$ to $O(m * n)$, with $O(m * n)$ space complexity.

def test(): View Source

36def test():
37    assert 2 + 2 == 4