LC 1143 [M] Longest Common Subsequence - ALawliet/algorithms GitHub Wiki

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @cache
        def dp(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            elif text1[i] == text2[j]:
                return 1 + dp(i+1, j+1)
            else:
                return max(dp(i+1, j), dp(i, j+1))

        return dp(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        T = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]
        
        for i in range(len(text1) - 1, -1, -1):
            for j in range(len(text2) - 1, -1, -1):
                if text1[i] == text2[j]:
                    T[i][j] = T[i+1][j+1] + 1
                else:
                    T[i][j] = max(T[i][j+1], T[i+1][j])
                    
        return T[0][0]