72. 编辑距离 (Hard)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/edit-distance/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你两个单词 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 由小写英文字母组成
题目详细分析
- 数据范围：长度 <= 500，O(m * n) 的 DP 约 25 万次操作，可以接受。
- 核心约束：三种操作代价都是 1（等权），目标是最少操作数。
- 边界条件：word1 为空则需要插入 len(word2) 次；word2 为空则需要删除 len(word1) 次。
- 隐藏条件：编辑距离是可逆的——将 word1 转 word2 的代价 = 将 word2 转 word1 的代价。插入和删除互为逆操作，所以可以只考虑”对 word1 操作”。
小白版直白理解
你有两个单词，想通过”改字母”、“加字母”、“删字母”三种操作把第一个变成第二个，每次操作算一步，问最少需要几步。这就像修改密码——你想把旧密码改成新密码，可以改某个字符、删掉某个字符或插入某个字符，每次操作算一次改动，想知道最少需要改几次。
解题思路
思路一：二维 DP（推荐）
核心洞察：dp[i][j] 表示 word1 前 i 个字符转换成 word2 前 j 个字符的最小编辑距离。对于每个子问题，我们有三种选择：
- 删除 word1 的最后一个字符 →
dp[i-1][j] + 1 - 插入 word2 的最后一个字符到 word1 →
dp[i][j-1] + 1 - 替换 或跳过（字符相等时不用替换）→
dp[i-1][j-1] + (0 或 1)
DP 五步法：
- dp 定义：
dp[i][j]表示 word1[0:i] → word2[0:j] 的最小编辑距离 - 递推公式：
- 字符相等：
dp[i][j] = dp[i-1][j-1] - 字符不等：
dp[i][j] = min(删除, 插入, 替换) + 1- 删除：
dp[i-1][j] + 1 - 插入：
dp[i][j-1] + 1 - 替换：
dp[i-1][j-1] + 1
- 删除：
- 字符相等：
- 初始化：
dp[i][0] = i（删除所有字符），dp[0][j] = j（插入所有字符） - 遍历顺序：从上到下、从左到右
- 举例验证：word1=“horse”, word2=“ros” →
"" 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 ← 答案 3
def minDistance(word1, word2):
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 # word1 删除所有字符
for j in range(n + 1):
dp[0][j] = j # word1 插入所有字符
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] = min(
dp[i - 1][j] + 1, # 删除 word1[i-1]
dp[i][j - 1] + 1, # 插入 word2[j-1]
dp[i - 1][j - 1] + 1 # 替换 word1[i-1] → word2[j-1]
)
return dp[m][n]思路二：空间优化 DP（一维 + 左上角暂存）
与 LCS 类似，dp[i][j] 依赖 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 三个方向。一维滚动需要额外保存左上角。
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # 初始化第 0 行：0, 1, 2, ..., n
for i in range(1, m + 1):
prev = dp[0] # 左上角 dp[i-1][j-1]
dp[0] = i # 每行第一个：dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # 保存当前值（将成为下一列的左上角）
if word1[i - 1] == word2[j - 1]:
dp[j] = prev # 相同，无需操作
else:
dp[j] = min(
dp[j] + 1, # 删除（来自上方）
dp[j - 1] + 1, # 插入（来自左方）
prev + 1 # 替换（来自左上角）
)
prev = temp # 更新左上角
return dp[n]思路三：递归 + 备忘录（自顶向下）
from functools import lru_cache
def minDistance(word1, word2):
@lru_cache(None)
def dfs(i, j):
if i == 0: # word1 为空，插入所有
return j
if j == 0: # word2 为空，删除所有
return i
if word1[i - 1] == word2[j - 1]:
return dfs(i - 1, j - 1) # 字符相同，跳过
return min(
dfs(i - 1, j) + 1, # 删除
dfs(i, j - 1) + 1, # 插入
dfs(i - 1, j - 1) + 1 # 替换
)
return dfs(len(word1), len(word2))易错点
- 边界初始化：
dp[i][0] = i和dp[0][j] = j必须正确设置。很多初学者忘记或赋值错误。 - 字符串索引偏移：
word1[i-1]与word2[j-1]比较，不是word1[i]与word2[j]。 - 三个操作的理解：删除是对 word1 删除（等价于对 word2 插入），插入是对 word1 插入（等价于对 word2 删除）。理解清楚可以减少困惑。
- 空间优化时左上角的处理：一维 DP 中需要用变量暂存
dp[j]的旧值作为下一列的左上角。
框架提炼
编辑距离 DP 模板（二维字符串 DP）：
def edit_distance(word1, word2):
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] = min(
dp[i - 1][j] + 1, # 删除
dp[i][j - 1] + 1, # 插入
dp[i - 1][j - 1] + 1 # 替换
)
return dp[m][n]这个模板可以泛化到各种字符串比较问题：
- 不同操作可以赋予不同权重（如替换代价 > 插入+删除）
- 可以增加操作类型（如交换相邻字符）
- 求最短编辑距离的过程可以回溯出具体操作步骤
关联题目
- 1143-最长公共子序列 — 相同二维 DP 结构，转移更少（只有匹配/跳过）
- 583-两个字符串的删除操作 — 只有删除操作的编辑距离（或：m + n - 2*LCS）
- 10-正则表达式匹配 — 更复杂的字符串匹配，需要考虑 * 和 . 通配符