Today's Challenge

https://leetcode.com/problems/longest-common-subsequence/

Longest Common Subsequence - LeetCode

전형적인 LCS 문제.
내부 함수를 써서 푼 솔루션을 참고

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def lcs(x, y, m, n, visited):
            k = (m, n)
            if m == 0 or n == 0:
                return 0
            if k not in visited:
                if x[m-1] == y[n-1]:
                    visited[k] = lcs(x, y, m-1, n-1, visited) + 1
                else:
                    a = lcs(x, y, m-1, n, visited)
                    b = lcs(x, y, m, n-1, visited)
                    visited[k] = max(a, b)
            return visited[k]
        x = len(text1)
        y = len(text2)
        visited = {}
        return lcs(text1, text2, x, y, visited)