Advertisement

LeetCode 编辑 距离 题目 号 72

阅读量：
在这里插入图片描述

注意的点：

1、边界条件应被限制在j+1或i+1的范围内

动态规划解题策略

复制代码 
    class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if not word1 or not word2: return len(word1) + len(word2)
        @cache
        def dp(i, j):
            if i == 0: return j + 1 - int(word1[0] in word2[: j+1]) 
            if j == 0: return i + 1 - int(word2[0] in word1[: i+1])
            if word1[i] == word2[j]: return dp(i-1, j-1)
            else: return min(dp(i-1, j-1), dp(i, j-1), dp(i-1, j))

全部评论 (0)

还没有任何评论哟~

相关文章推荐