# https://leetcode.com/problems/longest-common-subsequence/submissions/
class Solution_memo:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # conclusion: using self.memo DOESNT speed up
        # using global memo (outside of helper) DOESNT speed up
        # using array memo[][] over dict {} is FASTER & a LOT LESS space
        
        # using array instead of dict saves quite a lot of memory (140 MB to 25 MB) & a bit of speed
        self.memo = [[None for _ in range(len(text2))] for _ in range(len(text1))]
        def helper(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            
            if self.memo[i][j]: # (i, j) in memo:
                return self.memo[i][j] # memo[(i, j)]
            else:
                if text1[i] == text2[j]:
                    res = 1 + helper(i+1, j+1)
                else:
                    res = max(helper(i+1, j), helper(i, j+1))
                self.memo[i][j] = res # memo[(i, j)] = res
                return res
                
        return helper(0, 0)

class Solution_dp:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        dp = [[0 for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]
        
        for a in range(1, len(A) + 1):
            for b in range(1, len(B) + 1):
                if A[a-1] == B[b-1]:
                    dp[a][b] = 1 + dp[a-1][b-1]
                else:
                    dp[a][b] = max(
                        dp[a-1][b],
                        dp[a][b-1]
                    )
                    
        return dp[len(A)][len(B)]