1143. Longest Common Subsequence

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        # (i, j) = longest length
        # if text1[i] == text2[j]  (i, j) = 1 + (i - 1, j - 1)
        # else (i, j) = max((i - 1, j), (i, j - 1))


        # dp = [[0] * (len(text2) + 1) for _ in range((len(text1) + 1))]

        # for r in range(len(text1)):
        #     for c in range(len(text2)):
        #         if text1[r] == text2[c]:
        #             dp[r + 1][c + 1] = 1 + dp[r][c]
        #         else:
        #             dp[r + 1][c + 1] = max(dp[r][c + 1], dp[r + 1][c])


        # return dp[-1][-1]

        dp = [0] * (len(text2) + 1)

        for r in range(1, len(text1) + 1):
            temp = [0] * (len(text2) + 1)
            for c in range(1, len(text2) + 1):
                if text1[r - 1] == text2[c - 1]:
                    temp[c] = 1 + dp[c - 1]
                else:
                    temp[c] = max(dp[c], temp[c - 1])

            dp = temp

        return dp[-1]