当前位置：首页 > news >正文

LeetCode 72 编辑距离：python3 题解

news 2026/3/26 21:21:01

1. 题目理解
2. 解题思路：动态规划 (DP)
- 2.1 定义状态 (DP Table)
- 2.2 初始化 (Base Case)
- 2.3 状态转移方程 (核心逻辑)
- 2.4 图解示例 ("horse" -> "ros")
3. 代码实现
- 解法一：标准动态规划 (迭代)
- 解法二：记忆化递归 (Top-Down)
- 解法三：空间优化 (进阶)
4. 复杂度分析
5. 总结与建议

1. 题目理解

题目大意：
你有两个单词 word1 和 word2。你需要通过最少的操作次数，把 word1 变成 word2。
允许的操作有三种：

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

示例：

word1 = "horse", word2 = "ros"
输出：3
过程：horse -> rorse (替换 h->r) -> rose (删除 r) -> ros (删除 e)

核心难点：
这就好比你在写文档时打错了字，你要怎么改最省力？如果两个单词很长，人眼很难一眼看出最少步骤。计算机需要通过动态规划 (Dynamic Programming) 来一步步推导。

2. 解题思路：动态规划 (DP)

这道题是动态规划的经典入门题。为什么用 DP？因为要把长字符串变成另一个长字符串，可以拆解成：把短前缀变成短前缀 的子问题。

2.1 定义状态 (DP Table)

我们需要一个二维表格 dp。
定义 dp[i][j] 表示：word1 的前 i 个字符 转换成 word2 的前 j 个字符 所需的最少操作数。

i 的范围是 0 到 len(word1)
j 的范围是 0 到 len(word2)
注意：i=0 表示 word1 是空字符串，j=0 表示 word2 是空字符串。

2.2 初始化 (Base Case)

在开始比较字符之前，我们需要处理边界情况（空字符串）：

如果 word1 为空 (i=0)：
要把空串变成 word2 的前 j 个字符，只能插入 j 次。
所以：dp[0][j] = j
如果 word2 为空 (j=0)：
要把 word1 的前 i 个字符变成空串，只能删除 i 次。
所以：dp[i][0] = i

2.3 状态转移方程 (核心逻辑)

现在我们要填表格的中间部分。对于 word1 的第 i 个字符（即 word1[i-1]）和 word2 的第 j 个字符（即 word2[j-1]）：

情况 1：字符相同
如果 word1[i-1] == word2[j-1]：
不需要任何新操作，直接继承之前的结果。
dp[i][j] = dp[i-1][j-1]

情况 2：字符不同
如果 word1[i-1] != word2[j-1]：
我们需要从以下三种操作中选一个代价最小的，然后 +1（表示当前做了一次操作）：

替换 (Replace)：把 word1[i-1] 改成 word2[j-1]。
- 代价：dp[i-1][j-1] + 1
- 含义：前 i-1 和 j-1 已经匹配好了，最后一个字符替换一下即可。
删除 (Delete)：删除 word1[i-1]。
- 代价：dp[i-1][j] + 1
- 含义：word1 去掉当前字符后，剩下的 i-1 个字符去匹配 word2 的 j 个字符。
插入 (Insert)：在 word1 末尾插入 word2[j-1]。
- 代价：dp[i][j-1] + 1
- 含义：word1 的 i 个字符去匹配 word2 去掉当前字符后的 j-1 个字符（因为插入的字符已经匹配了 word2 的当前字符）。

综合公式：

if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]
else:dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

2.4 图解示例 ("horse" -> "ros")

假设 word1 = "horse", word2 = "ros"。表格大小 (5+1) x (3+1)。

	""	r	o	s
""	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

dp[0][0]=0: 空对空。
dp[1][1] ('h' vs 'r'): 不同。min(替换，删除，插入)+1 = min(0, 1, 1)+1 = 1。
...
最终右下角 dp[5][3] = 3 即为答案。

3. 代码实现

这里提供两种最常见的解法。

迭代法 (Bottom-Up)：推荐，效率高，无递归栈溢出风险。
记忆化搜索 (Top-Down)：逻辑更贴近人类直觉，但稍慢。

解法一：标准动态规划 (迭代)

这是最标准的解法，空间复杂度 \(O(M \times N)\)，时间复杂度 \(O(M \times N)\)。

class Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)# 1. 创建 DP 表格# 大小为 (m+1) x (n+1)，多出来的一行一列用于处理空字符串的情况dp = [[0] * (n + 1) for _ in range(m + 1)]# 2. 初始化边界条件# 当 word2 为空时，word1 需要删除 i 个字符for i in range(m + 1):dp[i][0] = i# 当 word1 为空时，需要插入 j 个字符才能变成 word2for j in range(n + 1):dp[0][j] = j# 3. 填充表格for i in range(1, m + 1):for j in range(1, n + 1):# 注意：dp[i] 对应的是 word1 的前 i 个字符# 所以当前比较的字符是 word1[i-1] 和 word2[j-1]if word1[i - 1] == word2[j - 1]:# 如果字符相同，不需要操作，直接继承左上角的值dp[i][j] = dp[i - 1][j - 1]else:# 如果字符不同，取三种操作的最小值 + 1# dp[i-1][j-1]: 替换# dp[i-1][j]:   删除 word1 的当前字符# dp[i][j-1]:   在 word1 插入 word2 的当前字符dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1# 4. 返回右下角的值，即完整单词的编辑距离return dp[m][n]

解法二：记忆化递归 (Top-Down)

如果你不习惯循环填表，递归可能更容易理解。为了防止重复计算，我们使用 memo 字典缓存结果。

class Solution:def minDistance(self, word1: str, word2: str) -> int:memo = {}def dp(i, j):# 如果状态已经计算过，直接返回if (i, j) in memo:return memo[(i, j)]# Base Case: 如果一个单词走完了，剩下的操作数就是另一个单词剩余的长度if i == 0:return jif j == 0:return i# 状态转移if word1[i - 1] == word2[j - 1]:# 字符相同，跳过res = dp(i - 1, j - 1)else:# 字符不同，取最小值 + 1res = min(dp(i - 1, j - 1), # 替换dp(i - 1, j),     # 删除dp(i, j - 1)      # 插入) + 1# 记录结果memo[(i, j)] = resreturn resreturn dp(len(word1), len(word2))

解法三：空间优化 (进阶)

观察状态转移方程，dp[i][j] 只依赖于 dp[i-1][...] 和 dp[i][...]。也就是说，我们只需要上一行的数据就可以计算当前行。
因此，我们可以把二维数组压缩成一维数组，将空间复杂度从 \(O(M \times N)\) 降低到 \(O(N)\)。

class Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)# 只需要一行数组，大小为 n+1# 初始状态相当于 dp[0][j] = jdp = list(range(n + 1))for i in range(1, m + 1):# prev 用于保存 dp[i-1][j-1] 的值 (即左上角的值)# 在更新 dp[j] 之前，dp[j] 存的是上一行的 dp[i-1][j]# 更新后，dp[j] 变成当前行的 dp[i][j]prev = dp[0] dp[0] = i  # 更新每行的第一个元素，相当于 dp[i][0] = ifor j in range(1, n + 1):temp = dp[j]  # 暂存当前的 dp[j]，因为它在下一轮循环中会变成左上角的值 (prev)if word1[i - 1] == word2[j - 1]:dp[j] = prevelse:# dp[j] (未更新前) 代表 dp[i-1][j] (删除)# dp[j-1] (已更新) 代表 dp[i][j-1] (插入)# prev 代表 dp[i-1][j-1] (替换)dp[j] = min(prev, dp[j], dp[j - 1]) + 1prev = temp # 更新 prev 为下一轮做准备return dp[n]

4. 复杂度分析

解法	时间复杂度	空间复杂度	说明
迭代 DP	\(O(M \times N)\)	\(O(M \times N)\)	最稳健，推荐面试使用
记忆化递归	\(O(M \times N)\)	\(O(M \times N)\)	逻辑清晰，但递归有栈开销
空间优化 DP	\(O(M \times N)\)	\(O(\min(M, N))\)	空间最优，适合内存受限场景