583.Delete Operation for Two Strings

#
# @lc app=leetcode.cn id=583 lang=python3
#
# [583] 两个字符串的删除操作
#

# @lc code=start
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        @cache
        def dfs(i, j):
            if i < 0 or j < 0:
                return 0
            if word1[i] == word2[j]:
                return dfs(i-1, j-1) + 1
            return max(dfs(i, j-1), dfs(i-1, j))
        a = dfs(n-1, m-1)
        return n-a+(m-a)
# @lc code=end

#
# @lc app=leetcode.cn id=583 lang=python3
#
# [583] 两个字符串的删除操作
#

# @lc code=start
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        # @cache
        # def dfs(i, j):
        #     if i < 0 or j < 0:
        #         return 0
        #     if word1[i] == word2[j]:
        #         return dfs(i-1, j-1) + 1
        #     return max(dfs(i, j-1), dfs(i-1, j))
        # a = dfs(n-1, m-1)
        # return n-a+(m-a)
        f = [[0] * (m+1) for _ in range(n+1)]
        for i, x in enumerate(word1):
            for j, y in enumerate(word2):
                # 这里不加一
                if word1[i] == word2[j]:
                    f[i+1][j+1] = f[i][j] + 1
                else:
                    f[i+1][j+1] = max(f[i+1][j], f[i][j+1])
        return f[n][m]

# @lc code=end