摘要编辑距离是衡量两个字符串相似度的经典指标也是动态规划领域的核心问题之一。本文深入解析LeetCode第72题详细推导状态转移方程从递归暴力解法逐步优化到自顶向下的记忆化搜索和自底向上的动态规划。通过图解和代码对比帮助读者彻底理解这一经典问题的本质并延伸探讨编辑距离在拼写检查、DNA序列比对等领域的实际应用。一、问题定义与背景1.1 问题描述给你两个单词word1和word2请计算将word1转换成word2所需的最少操作数。你可以对一个单词进行以下三种操作插入Insert插入一个字符删除Delete删除一个字符替换Replace将一个字符替换成另一个字符示例 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 → exention (将 i 替换为 e) exention → exection (将 n 替换为 c) exection → execution (插入 u) execution → execution (将 i 替换为 e)1.2 问题的本质编辑距离问题的本质是字符串对齐和操作成本优化。我们需要找到一条从word1到word2的最优转换路径使得总操作次数最少。1.3 应用场景拼写纠错计算用户输入与正确单词的编辑距离DNA序列比对衡量两条DNA链的相似度论文查重文本相似度检测机器翻译评估翻译质量二、问题分析2.1 问题分解将word1[0...i]转换为word2[0...j]的问题可以分解为情况分析考虑最后一个字符当word1[i] word2[j]时问题退化为word1[0...i-1]→word2[0...j-1]无需额外操作当word1[i] ! word2[j]时替换操作将word1[i]替换为word2[j]问题转化为word1[0...i-1]→word2[0...j-1]插入操作在word1[0...i]末尾插入word2[j]问题转化为word1[0...i]→word2[0...j-1]删除操作删除word1[i]问题转化为word1[0...i-1]→word2[0...j]2.2 状态定义定义dp[i][j]为将word1[0...i-1]前 i 个字符转换为word2[0...j-1]前 j 个字符所需的最少操作数。注意这里使用i和j表示前缀长度便于处理空串情况。三、动态规划解法3.1 状态转移方程根据问题分解可以得到状态转移方程dp[i][j]{dp[i−1][j−1]if word1[i−1]word2[j−1]min⁡(dp[i−1][j]1,if word1[i−1]≠word2[j−1]dp[i][j−1]1,dp[i−1][j−1]1)dp[i][j] \begin{cases} dp[i-1][j-1] \text{if } word1[i-1] word2[j-1] \\ \min(dp[i-1][j] 1, \text{if } word1[i-1] \neq word2[j-1] \\ \quad dp[i][j-1] 1, \\ \quad dp[i-1][j-1] 1) \end{cases}dp[i][j]⎩⎨⎧​dp[i−1][j−1]min(dp[i−1][j]1,dp[i][j−1]1,dp[i−1][j−1]1)​ifword1[i−1]word2[j−1]ifword1[i−1]word2[j−1]​其中dp[i-1][j] 1删除word1[i-1]然后将word1[0...i-2]转换为word2[0...j-1]dp[i][j-1] 1在word1[0...i-1]后插入word2[j-1]然后将word1[0...i-1]转换为word2[0...j-2]dp[i-1][j-1] 1将word1[i-1]替换为word2[j-1]3.2 初始化dp[0][j] j将空串转换为word2[0...j-1]需要 j 次插入操作dp[i][0] i将word1[0...i-1]转换为空串需要 i 次删除操作dp[0][0] 0空串到空串0 次操作3.3 完整代码实现defminDistance(word1:str,word2:str)-int: 动态规划解决编辑距离问题 时间复杂度O(mn)其中 m, n 分别是两个字符串的长度 空间复杂度O(mn) m,nlen(word1),len(word2)# 创建 dp 表(m1) x (n1)dp[[0]*(n1)for_inrange(m1)]# 初始化第一行将空串转换为 word2[0...j-1]forjinrange(n1):dp[0][j]j# 初始化第一列将 word1[0...i-1] 转换为空串foriinrange(m1):dp[i][0]i# 填充 dp 表foriinrange(1,m1):forjinrange(1,n1):ifword1[i-1]word2[j-1]:# 最后一个字符相同无需操作dp[i][j]dp[i-1][j-1]else:# 三种操作取最小值 1dp[i][j]min(dp[i-1][j]1,# 删除dp[i][j-1]1,# 插入dp[i-1][j-1]1# 替换)returndp[m][n]3.4 算法图解以word1 horse,word2 ros为例 r o s ┌─────┬─────┬─────┬─────┐ │ 0 │ 1 │ 2 │ 3 │ ← dp[0][j] j ├─────┼─────┼─────┼─────┤ h │ 1 │ 1 │ 2 │ 3 │ ← dp[1][0] i ├─────┼─────┼─────┼─────┤ ho│ 2 │ 2 │ 1 │ 2 │ ├─────┼─────┼─────┼─────┤ hor│ 3 │ 3 │ 2 │ 2 │ ├─────┼─────┼─────┼─────┤ hors│ 4 │ 4 │ 3 │ 2 │ ├─────┼─────┼─────┼─────┤ horse│ 5 │ 5 │ 4 │ 3 │ ← 最终答案 └─────┴─────┴─────┴─────┘填充过程以dp[5][3]为例word1[4] e,word2[2] s不匹配dp[4][3] 1 3 1 4删除 ‘e’dp[5][2] 1 4 1 5插入 ‘s’dp[4][2] 1 3 1 4将 ‘e’ 替换为 ‘s’min(4, 5, 4) 3四、空间优化4.1 滚动数组优化观察 DP 表可知dp[i][j]只依赖于dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]即只与上一行和当前行的前一个元素有关。因此可以将空间优化到O(n)O(n)O(n)defminDistance_optimized(word1:str,word2:str)-int: 空间优化的动态规划 时间复杂度O(mn) 空间复杂度O(n) m,nlen(word1),len(word2)# 只保留上一行和当前行prevlist(range(n1))# dp[0][*]foriinrange(1,m1):curr[i][0]*n# dp[i][0] iforjinrange(1,n1):ifword1[i-1]word2[j-1]:curr[j]prev[j-1]else:curr[j]min(prev[j]1,# 从上方来删除curr[j-1]1,# 从左方来插入prev[j-1]1# 从左上方来替换)prevcurrreturnprev[n]4.2 优化原理图解原始二维表 j→ ┌─────┬─────┬─────┐ i ↓ │ ← ← │ ← ← │ ← ← │ ├─────┼─────┼─────┤ │ ↖ ↖ │ ↖ ↖ │ ↖ ↖ │ ├─────┼─────┼─────┤ │ ← ← │ ← ← │ ← ← │ └─────┴─────┴─────┘ 优化后只保留两行 prev: dp[i-1][*] curr: dp[i][*]五、递归 记忆化5.1 自顶向下的思路我们也可以从递归的角度思考定义minDist(i, j)为将word1[i...]转换为word2[j...]的最少操作数。fromfunctoolsimportlru_cachedefminDistance_recursive(word1:str,word2:str)-int: 递归 记忆化搜索 时间复杂度O(mn) 空间复杂度O(mn) m,nlen(word1),len(word2)lru_cache(maxsizeNone)defminDist(i:int,j:int)-int:# base case空串处理ifim:returnn-j# 需要插入剩余的字符ifjn:returnm-i# 需要删除剩余的字符ifword1[i]word2[j]:returnminDist(i1,j1)else:return1min(minDist(i1,j),# 删除 word1[i]minDist(i,j1),# 插入 word2[j]minDist(i1,j1)# 替换)returnminDist(0,0)5.2 递归树与记忆化minDist(0, 0) / | \ del(1,0) ins(0,1) rep(1,1) | | | minDist(1,0) minDist(0,1) minDist(1,1) ... ... ... 使用 lru_cache 后重复的子问题只计算一次六、变种与扩展6.1 打印编辑路径不仅要知道最小操作数还要知道具体的编辑操作defminDistanceWithPath(word1:str,word2:str)-tuple:返回最小编辑距离和编辑操作序列m,nlen(word1),len(word2)# 构建 DP 表dp[[0]*(n1)for_inrange(m1)]foriinrange(m1):dp[i][0]iforjinrange(n1):dp[0][j]jforiinrange(1,m1):forjinrange(1,n1):ifword1[i-1]word2[j-1]:dp[i][j]dp[i-1][j-1]else:dp[i][j]1min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])# 回溯找出编辑路径operations[]i,jm,nwhilei0orj0:ifi0andj0andword1[i-1]word2[j-1]:operations.append(f保持: {word1[i-1]})i-1j-1elifi0anddp[i][j]dp[i-1][j]1:operations.append(f删除: {word1[i-1]})i-1elifj0anddp[i][j]dp[i][j-1]1:operations.append(f插入: {word2[j-1]})j-1else:operations.append(f替换: {word1[i-1]} → {word2[j-1]})i-1j-1operations.reverse()returndp[m][n],operations# 示例distance,opsminDistanceWithPath(horse,ros)print(f编辑距离:{distance})print(编辑操作:)foropinops:print(f{op})6.2 编辑距离阈值有时我们只需要知道编辑距离是否小于某个阈值defwithinEditDistance(word1:str,word2:str,threshold:int)-bool: 判断两个字符串的编辑距离是否在阈值内 如果编辑距离大于阈值提前终止搜索 m,nlen(word1),len(word2)# 剪枝如果长度差大于阈值直接返回 Falseifabs(m-n)threshold:returnFalse# 优化的一维 DPprevlist(range(n1))foriinrange(1,m1):curr[i][0]*n min_vali# 当前行最小值的下界forjinrange(1,n1):ifword1[i-1]word2[j-1]:curr[j]prev[j-1]else:curr[j]1min(prev[j],curr[j-1],prev[j-1])min_valmin(min_val,curr[j])# 剪枝如果当前行最小值已超过阈值ifmin_valthreshold:returnFalseprevcurrreturnprev[n]threshold6.3 带权重的编辑距离不同操作可以有不同的成本defweightedEditDistance(word1:str,word2:str,insert_cost:int1,delete_cost:int1,replace_cost:int1)-int: 带权重的编辑距离 insert_cost: 插入成本 delete_cost: 删除成本 replace_cost: 替换成本可设为0表示允许不匹配 m,nlen(word1),len(word2)dp[[0]*(n1)for_inrange(m1)]forjinrange(n1):dp[0][j]j*insert_costforiinrange(m1):dp[i][0]i*delete_costforiinrange(1,m1):forjinrange(1,n1):ifword1[i-1]word2[j-1]:dp[i][j]dp[i-1][j-1]else:dp[i][j]min(dp[i-1][j]delete_cost,dp[i][j-1]insert_cost,dp[i-1][j-1]replace_cost)returndp[m][n]七、复杂度分析总结解法时间复杂度空间复杂度特点暴力递归O(3mn)O(3^{mn})O(3mn)O(mn)O(mn)O(mn)指数级不可行记忆化递归O(mn)O(mn)O(mn)O(mn)O(mn)O(mn)代码直观二维 DPO(mn)O(mn)O(mn)O(mn)O(mn)O(mn)表格清晰一维 DPO(mn)O(mn)O(mn)O(min⁡(m,n))O(\min(m,n))O(min(m,n))空间优化阈值剪枝最好O(k)O(k)O(k)O(min⁡(m,n))O(\min(m,n))O(min(m,n))k 为阈值八、面试总结核心要点状态定义dp[i][j]表示将word1[0...i-1]转换为word2[0...j-1]的最少操作数状态转移分字符相同/不同两种情况字符不同时取删除/插入/替换的最小值初始化空串的处理第一行和第一列空间优化从二维表优化到一维数组面试话术“编辑距离是经典的二维动态规划问题。我定义dp[i][j]表示将word1的前i个字符转换为word2的前j个字符的最少操作数。当最后一个字符相同时问题退化为子问题当不同时需要考虑删除、插入、替换三种操作取最小值加一。时间复杂度O(mn)O(mn)O(mn)空间可以用滚动数组优化到O(n)O(n)O(n)。”延伸问题面试官可能追问如何打印具体的编辑操作回溯 DP 表如何优化到O(k)O(k)O(k)的提前终止阈值剪枝如何处理带权重的操作成本修改转移方程参考文献LeetCode. (2024). 72. Edit Distance. https://leetcode.com/problems/edit-distance/Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady.Wagner, R. A., Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM.