编辑距离

难度: Medium

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

Submission

运行时间: 112 ms

内存: 17.5 MB

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        memo = dict()

        def dp(i, j):
            if (i, j) in memo:
                return memo[(i, j)]
            if i == -1:
                return j + 1
            if j == -1:
                return i + 1

            if word1[i] ==  word2[j]:
                res = dp(i-1, j-1)
            else:
                res = min(
                    dp(i, j-1)+1,  # 插入
                    dp(i-1, j)+1,  # 删除
                    dp(i-1, j-1) + 1  # 替换
                )
            memo[(i, j)] = res
            return res

        return dp(len(word1)-1, len(word2)-1)

Explain

这是一道经典的动态规划题目。题解使用了带备忘录的递归方式实现动态规划。主要思路是，定义dp(i, j)表示将word1[0:i]转换为word2[0:j]的编辑距离，则dp(i, j)可以从以下三种情况转移而来：1. dp(i-1, j-1)，若当前字符word1[i]==word2[j]，则不需要操作；2. dp(i-1, j) + 1，相当于在word1[i]后面插入一个字符word2[j]；3. dp(i, j-1) + 1，相当于在word1[i]后面删除一个字符；4. dp(i-1, j-1) + 1，将word1[i]替换为word2[j]。递归公式为dp(i, j) = min(dp(i-1, j-1), dp(i-1, j)+1, dp(i, j-1)+1, dp(i-1, j-1)+1)。边界条件为当i=-1时，相当于word1为空，需要插入j+1个字符，dp(i, j)=j+1；当j=-1时，相当于word2为空，需要删除i+1个字符，dp(i, j)=i+1。为了避免重复计算，使用了备忘录memo存储已计算过的dp值。

时间复杂度: O(mn)

空间复杂度: O(mn)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        memo = dict()

        def dp(i, j):
            if (i, j) in memo:                  # 如果memo中已经计算过，直接返回
                return memo[(i, j)]
            if i == -1:                         # word1为空的情况  
                return j + 1
            if j == -1:                         # word2为空的情况
                return i + 1

            if word1[i] ==  word2[j]:           # 当前字符相同，不需要操作
                res = dp(i-1, j-1) 
            else:
                res = min(
                    dp(i, j-1)+1,  # 插入字符
                    dp(i-1, j)+1,  # 删除字符
                    dp(i-1, j-1) + 1  # 替换字符
                )
            memo[(i, j)] = res                  # 将结果保存到备忘录
            return res

        return dp(len(word1)-1, len(word2)-1)

Explore

在`dp(i, j)`函数中，选择`i == -1`和`j == -1`作为基准情况用于表示字符串`word1`或`word2`已经完全处理完毕（即已经为空）。当`i == -1`时，意味着要将一个空的`word1`转换为`word2[0:j]`，这需要添加`j+1`个字符。同样，当`j == -1`时，意味着将`word1[0:i]`转换为一个空的`word2`，这需要删除`i+1`个字符。这些基准情况是边界条件，提供了递归过程中必要的停止点。如果选择`i == 0`或`j == 0`作为基准情况，虽然可以表示单个字符与空字符串的关系，但不足以完整表达整个字符串与空字符串之间的转换关系。

确实，题解中的公式存在重复，`dp(i-1, j-1)`被重复了两次。正确的递归公式应该是`dp(i, j) = min(dp(i-1, j-1) + (1 if word1[i] != word2[j] else 0), dp(i-1, j) + 1, dp(i, j-1) + 1)`。这里，如果`word1[i]`和`word2[j]`字符不同，则`dp(i-1, j-1)`需要增加1来表示替换操作；否则，如果字符相同，则不增加额外成本。

当`word1[i]`与`word2[j]`不同，选择使用`dp(i-1, j-1) + 1`是因为这表示最直接的替换操作——即将`word1[i]`直接替换成`word2[j]`，从而使两个字符串在这一位置匹配。这是一种高效的方式来处理字符不匹配的情况，因为它直接解决了不匹配的问题，而不是通过插入或删除间接调整。插入或删除虽然也可以达到目的，但它们通常需要更多步骤或更复杂的操作来实现两字符串的匹配。