72. 编辑距离

题目链接（中等）

题目描述

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

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

• 插入一个字符；
• 删除一个字符；
• 替换一个字符。

数据范围：

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

示例

示例 1：

输入： word1 = "horse", word2 = "ros"
输出： 3

示例 2：

输入： word1 = "intention", word2 = "execution"
输出： 5

方法一：动态规划

思路及解法

设 dp[i][j] 表示 word1 的前 i 个字符和 word2 的前 j 个字符之间的编辑距离。

虽然对两个单词各有插入、删除、替换三种操作，但可以证明本质上只有三种不同的操作：

• 在 word1 中插入一个字符，等价于在 word2 中删除一个字符；
• 在 word2 中插入一个字符，等价于在 word1 中删除一个字符；
• 修改 word1 中的一个字符，等价于修改 word2 中的对应字符。

因此，在推导状态转移时，只需要考虑以下三种情况：

1. 在 word1 末尾插入一个字符：先让 word1[0..i-1] 变成 word2[0..j-2]，再补上 word2[j-1]，代价为 dp[i][j-1] + 1；
2. 在 word2 末尾插入一个字符：等价于删除 word1[i-1]，代价为 dp[i-1][j] + 1；
3. 修改 word1[i-1] 为 word2[j-1]：代价为 dp[i-1][j-1] + 1。若 word1[i-1] == word2[j-1]，则不需要修改，代价为 dp[i-1][j-1]。

综合得到转移方程：

$$dp[i][j] = \begin{cases} \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1] - 1) + 1, & word1[i-1] = word2[j-1] \\[6pt] \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]) + 1, & word1[i-1] \neq word2[j-1] \end{cases}$$

边界条件：

• dp[i][0] = i：word1 前 i 个字符变成空串，需要删除 i 次；
• dp[0][j] = j：空串变成 word2 前 j 个字符，需要插入 j 次；
• dp[0][0] = 0。

直觉理解：从左上角走到右下角，每个格子 dp[i][j] 对应把 word1 前 i 个字符变成 word2 前 j 个字符的最小代价。当前字符相同时不需要额外操作，直接继承左上角；不同时，从上、左、左上三个方向取最小再加 1。

代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i

        for j in range(n+1):
            dp[0][j] = j

        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1+ min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1])
        return dp[m][n]

复杂度分析

• 时间复杂度：$O(mn)$，其中 $m$、$n$ 分别为 word1、word2 的长度。需要填充整个 dp 表。
• 空间复杂度：$O(mn)$，二维 dp 数组。

方法二：动态规划（滚动数组）

思路及解法

观察转移方程 dp[i][j] 只依赖三个位置：dp[i-1][j]（上一行同列）、dp[i][j-1]（本行左列）、dp[i-1][j-1]（左上角）。

因此可以把二维 dp 压成一维数组：

• dp[j] 在更新前表示 dp[i-1][j]；
• dp[j-1] 在更新后表示 dp[i][j-1]；
• prev 记录 dp[i-1][j-1]（上一次循环的 dp[j-1]，也就是左上角）。

因为每次更新的 dp[j-1] 会覆盖左上角，所以需要用一个变量 prev 暂存旧的 dp[j-1]（即 dp[i-1][j-1]）。

代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        if n * m == 0:
            return n + m

        # dp[j] 表示当前行 word1 前 i 个字符与 word2 前 j 个字符的编辑距离
        dp = list(range(m + 1))

        for i in range(1, n + 1):
            prev = dp[0]        # 对应 dp[i-1][0]
            dp[0] = i           # 当前行第 0 列
            for j in range(1, m + 1):
                temp = dp[j]    # 暂存 dp[i-1][j]
                if word1[i - 1] == word2[j - 1]:
                    dp[j] = min(dp[j] + 1, dp[j - 1] + 1, prev)
                else:
                    dp[j] = min(dp[j] + 1, dp[j - 1] + 1, prev + 1)
                prev = temp     # 变成下一轮的左上角

        return dp[m]

也可以选择较短的一个串作为内层循环，进一步降低空间到 $O(\min(m, n))$，不过本题数据量小，没必要。

复杂度分析

• 时间复杂度：$O(mn)$。
• 空间复杂度：$O(\min(m, n))$，只保留一行状态。