【笔面试算法学习专栏】编辑距离：72.编辑距离

摘要

编辑距离是衡量两个字符串相似度的经典指标，也是动态规划领域的核心问题之一。本文深入解析LeetCode第72题，详细推导状态转移方程，从递归暴力解法逐步优化到自顶向下的记忆化搜索和自底向上的动态规划。通过图解和代码对比，帮助读者彻底理解这一经典问题的本质，并延伸探讨编辑距离在拼写检查、DNA序列比对等领域的实际应用。

一、问题定义与背景

1.1 问题描述

给你两个单词word1和word2，请计算将word1转换成word2所需的最少操作数。

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

1. 插入（Insert）：插入一个字符
2. 删除（Delete）：删除一个字符
3. 替换（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]的问题可以分解为：

情况分析（考虑最后一个字符）：

1. 当word1[i] == word2[j]时

   • 问题退化为：word1[0...i-1]→word2[0...j-1]
   • 无需额外操作

2. 当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,n=len(word1),len(word2)# 创建 dp 表，(m+1) x (n+1)dp=[[0]*(n+1)for_inrange(m+1)]# 初始化第一行：将空串转换为 word2[0...j-1]forjinrange(n+1):dp[0][j]=j# 初始化第一列：将 word1[0...i-1] 转换为空串foriinrange(m+1):dp[i][0]=i# 填充 dp 表foriinrange(1,m+1):forjinrange(1,n+1):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,n=len(word1),len(word2)# 只保留上一行和当前行prev=list(range(n+1))# dp[0][*]foriinrange(1,m+1):curr=[i]+[0]*n# dp[i][0] = iforjinrange(1,n+1):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# 从左上方来（替换）)prev=currreturnprev[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,n=len(word1),len(word2)@lru_cache(maxsize=None)defminDist(i:int,j:int)->int:# base case：空串处理ifi==m:returnn-j# 需要插入剩余的字符ifj==n:returnm-i# 需要删除剩余的字符ifword1[i]==word2[j]:returnminDist(i+1,j+1)else:return1+min(minDist(i+1,j),# 删除 word1[i]minDist(i,j+1),# 插入 word2[j]minDist(i+1,j+1)# 替换)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,n=len(word1),len(word2)# 构建 DP 表dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(m+1):dp[i][0]=iforjinrange(n+1):dp[0][j]=jforiinrange(1,m+1):forjinrange(1,n+1):ifword1[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])# 回溯找出编辑路径operations=[]i,j=m,nwhilei>0orj>0:ifi>0andj>0andword1[i-1]==word2[j-1]:operations.append(f"保持: '{word1[i-1]}'")i-=1j-=1elifi>0anddp[i][j]==dp[i-1][j]+1:operations.append(f"删除: '{word1[i-1]}'")i-=1elifj>0anddp[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,ops=minDistanceWithPath("horse","ros")print(f"编辑距离:{distance}")print("编辑操作:")foropinops:print(f"{op}")

6.2 编辑距离阈值

有时我们只需要知道编辑距离是否小于某个阈值：

defwithinEditDistance(word1:str,word2:str,threshold:int)->bool:""" 判断两个字符串的编辑距离是否在阈值内 如果编辑距离大于阈值，提前终止搜索 """m,n=len(word1),len(word2)# 剪枝：如果长度差大于阈值，直接返回 Falseifabs(m-n)>threshold:returnFalse# 优化的一维 DPprev=list(range(n+1))foriinrange(1,m+1):curr=[i]+[0]*n min_val=i# 当前行最小值的下界forjinrange(1,n+1):ifword1[i-1]==word2[j-1]:curr[j]=prev[j-1]else:curr[j]=1+min(prev[j],curr[j-1],prev[j-1])min_val=min(min_val,curr[j])# 剪枝：如果当前行最小值已超过阈值ifmin_val>threshold:returnFalseprev=currreturnprev[n]<=threshold

6.3 带权重的编辑距离

不同操作可以有不同的成本：

defweightedEditDistance(word1:str,word2:str,insert_cost:int=1,delete_cost:int=1,replace_cost:int=1)->int:""" 带权重的编辑距离 insert_cost: 插入成本 delete_cost: 删除成本 replace_cost: 替换成本（可设为0表示允许不匹配） """m,n=len(word1),len(word2)dp=[[0]*(n+1)for_inrange(m+1)]forjinrange(n+1):dp[0][j]=j*insert_costforiinrange(m+1):dp[i][0]=i*delete_costforiinrange(1,m+1):forjinrange(1,n+1):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]

七、复杂度分析总结

八、面试总结

核心要点

1. 状态定义：dp[i][j]表示将word1[0...i-1]转换为word2[0...j-1]的最少操作数
2. 状态转移：分字符相同/不同两种情况，字符不同时取删除/插入/替换的最小值
3. 初始化：空串的处理（第一行和第一列）
4. 空间优化：从二维表优化到一维数组

面试话术

“编辑距离是经典的二维动态规划问题。我定义dp[i][j]表示将word1的前i个字符转换为word2的前j个字符的最少操作数。当最后一个字符相同时，问题退化为子问题；当不同时，需要考虑删除、插入、替换三种操作，取最小值加一。时间复杂度O(mn)O(mn)O(mn)，空间可以用滚动数组优化到O(n)O(n)O(n)。”

延伸问题

面试官可能追问：

1. 如何打印具体的编辑操作？（回溯 DP 表）
2. 如何优化到O(k)O(k)O(k)的提前终止？（阈值剪枝）
3. 如何处理带权重的操作成本？（修改转移方程）

参考文献

1. LeetCode. (2024). 72. Edit Distance. https://leetcode.com/problems/edit-distance/
2. Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady.
3. Wagner, R. A., & Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM.