583. Delete Operation for Two Strings

583. Delete Operation for Two Strings

兩個單字需要刪掉的字元，恰好是他們沒有重疊的字元，他們沒有重疊的字元，所以找出兩個字元的最長公共子字串，分別刪掉後，剩下的字元就是最少的刪除操作了。

class Solution:
    def longestCommonSubsequence(self, word1: str, word2: str) -> int:
        @lru_cache(None)
        def helper(i, j):
            if i == len(word1) or j == len(word2):
                return 0
            if word1[i] == word2[j]:
                return 1 + helper(i+1, j+1)
            else:
                return max(helper(i+1, j), helper(i, j+1))
        return helper(0, 0)


    def minDistance(self, word1: str, word2: str) -> int:
        lcs = self.longestCommonSubsequence(word1, word2)

        return len(word1) + len(word2) - 2 * lcs