1143. Longest Common Subsequence

mian.py

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        # top down approach: function dp
        # state variables are (i, j) where i is index of text1 and j is index of text2
        # if both carachters are equal retrun 1 
        # else choose the max between the two remaining
        
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == -1 or j == -1:
                return 0
            
            if text1[i] == text2[j]:
                return 1 + dp(i-1, j-1)
            else:
                return max(dp(i, j-1), dp(i-1, j))
            
                
        
        return dp(len(text1)-1, len(text2)-1)
    
    
        # bottom up
#         dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        
#         for i in range(len(text2)-1, -1, -1):
#             for j in range(len(text1)-1, -1, -1):
#                 if text2[i] == text1[j] :
#                     dp[j][i] = 1 + dp[j+1][i+1]
#                 else:
#                     dp[j][i] = max(dp[j+1][i], dp[j][i+1])

#         return dp[0][0]