Today's Challenge

https://leetcode.com/problems/delete-operation-for-two-strings/

Delete Operation for Two Strings - LeetCode

오늘은 LCS 관련 문제였다.
솔루션 소스가 너무 간단해서 놀람.. 이렇게 간단할 줄이야

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m,n=len(word1),len(word2)
        @cache
        def lcs(i, j):
            if i==m or j==n:
                return 0            
            return 1 + lcs(i+1, j+1) if word1[i]==word2[j] else  max(lcs(i+1, j), lcs(i,j+1))                               
        return m + n - 2*lcs(0,0)