[LeetCode][python3]Day26. Longest Common Subsequence (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.28

1. A Common Solution

class Solution:
    def longestCommonSubsequence(self, str1: str, str2: str) -> int:
        a = len(str1)
        b = len(str2)
        string_matrix = [[0 for i in range(b+1)] for i in range(a+1)]   
        for i in range(1, a+1):
            for j in range(1, b+1):
                if i == 0 or j == 0:
                    string_matrix[i][j] = 0
                elif str1[i-1] == str2[j-1]:
                    string_matrix[i][j] = 1+string_matrix[i-1][j-1]
                else:
                    string_matrix[i][j] = max(string_matrix[i-1][j], string_matrix[i][j-1])
        index = string_matrix[a][b]
        res = [""] * index
        i = a
        j = b
        while i > 0 and j > 0:
            if str1[i-1] == str2[j-1]:
                res[index-1] = str1[i-1]
                i -= 1
                j -= 1
                index -= 1
            elif string_matrix[i-1][j] > string_matrix[i][j-1]:
                i -= 1
            else:
                j -= 1
        return len(res)

Explanation:

It is a bit busy these days. I’ll find some time to add the explanation here.

2. A Dynamic Programming Solution

class Solution:
    def longestCommonSubsequence(self,text1: str,text2: str) -> int:
        memo = collections.defaultdict(list)
        for i, a in enumerate(text1):
            memo[a].append(i)
        tmp = []
        for c in text2:
            tmp += memo[c][::-1]
            
        # print(tmp)
        def lis(arr):
            dp = [-1]
            for n in arr:
                if n > dp[-1]:
                    dp.append(n)
                else:
                    idx = bisect.bisect_left(dp, n)
                    dp[idx] = n
            return len(dp) - 1
        return lis(tmp)

Explanation:

It is a bit busy these days. I’ll find some time to add the explanation here.