Solutions

# Top down or bottom up DP by using 2 pointers to keep track of the current index in each string. If the characters match, we can move both pointers and add 1 to the result. If they don't match, we can move either pointer and take the max of the two results. 
# dp


# Top down DP - O(n*m) time, O(n*m) space
# w/o memoization: O(2^(n+m)) time, O(m+n) space
def longestCommonSubsequence(text1: str, text2: str) -> int:
    dp = {}

    def dfs(i1: int, i2: int) -> int:
        if i1 >= len(text1) or i2 >= len(text2):
            return 0
        if (i1, i2) in dp:
            return dp[(i1, i2)]

        if text1[i1] == text2[i2]:
            dp[(i1,i2)] = 1 + dfs(i1+1, i2+1)
        else:
            dp[(i1,i2)] = max(dfs(i1, i2+1), dfs(i1+1, i2))
        return dp[(i1,i2)]

    return dfs(0, 0)

    
# Bottom-up DP - O(n*m) time, O(n*m) space
def longestCommonSubsequence(text1: str, text2: str) -> int:

    # dp[i][j] = length of longest common subsequence for substring text1[i:] and text2[j:]
    # NB: (n+1)x(m+1) matrix to account for empty string comparison
    dp = [[0 for _ in range(len(text2)+1)] 
                for _ 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]:
                dp[i][j] = 1 + dp[i+1][j+1]
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j+1])

    return dp[0][0]