72.编辑距离

链接：72.编辑距离
难度：Medium
标签：字符串、动态规划
简介：给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

题解 1 - python

• 编辑时间：2023-10-23
• 执行用时：84ms
• 内存消耗：18.8MB
• 编程语言：python
• 解法介绍：dp判断每种情况下的最小操作数。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1, n2 = len(word1), len(word2)
        @cache
        def dfs(i1: int, i2: int) -> int:
            if i1 == n1: return n2 - i2
            if i2 == n2: return n1 - i1
            if word1[i1] == word2[i2]: return dfs(i1 + 1, i2 + 1)
            return min(
                dfs(i1 + 1, i2) + 1,    # i1 删除一个字符
                dfs(i1, i2 + 1) + 1,    # i1 插入一个字符
                dfs(i1 + 1, i2 + 1) + 1 # i1 替换一个字符
            )
        return dfs(0, 0)