编辑距离是字符串处理中的经典问题，衡量将一个字符串变成另一个字符串所需的最少操作数。
问题定义#
给定两个字符串 A 和 B，求出将 A 变为 B 的最小操作数。
每次只允许一种操作，每个操作的 “代价” 为 1。
- 插入一个字符（Insert）
- 删除一个字符（Delete）
- 替换一个字符（Replace）
示例：
将 horse 变成 ros:
horse → rorse （替换 'h' → 'r'）
rorse → rose （删除 'r'）
rose → ros （删除 'e'）
总共 3 步 → 编辑距离 = 3
动态规划求解#
我们使用一个二维数组 表示： 转换为 所需的最小操作数
## 初始条件
dp[0][j] = j # 把空串变成 B[0..j-1]：插入 j 次
dp[i][0] = i # 把 A[0..i-1] 变成空串：删除 i 次
## 状态转移方程
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] # 不需要操作
else:
dp[i][j] = min(
dp[i-1][j] + 1, # 删除 A[i-1]
dp[i][j-1] + 1, # 插入 B[j-1]
dp[i-1][j-1] + 1 # 替换 A[i-1] 为 B[j-1]
)
伪码：
def edit_distance(A, B):
n, m = len(A), len(B)
dp = [[0] * (m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = j
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[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[n][m]
时间复杂度
空间复杂度
可以使用滚动数组优化空间复杂度，只需保存当前行和前一行即可。这与最长公共子序列问题 LCS 类似。
变体问题#
最短编辑路径问题 （需要恢复编辑操作）
带权编辑距离问题 （每种操作的代价不同）
Damerau-Levenshtein 距离（DL 距离，允许交换操作）
编辑路径恢复（回溯）#
需要额外构造一个数组，保存操作步骤。
def edit_path(A, B):
n, m = len(A), len(B)
dp = [[0]*(m+1) for _ in range(n+1)]
move = [['']*(m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = i
move[i][0] = 'D' # 删除
for j in range(m+1):
dp[0][j] = j
move[0][j] = 'I' # 插入
move[0][0] = ' '
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1]
move[i][j] = 'M' # 匹配
else:
choices = [
(dp[i-1][j] + 1, 'D'),
(dp[i][j-1] + 1, 'I'),
(dp[i-1][j-1] + 1, 'R')
]
dp[i][j], move[i][j] = min(choices)
# 回溯路径
ops = []
i, j = n, m
while i > 0 or j > 0:
op = move[i][j]
if op == 'M' or op == 'R':
ops.append((op, i-1, j-1))
i -= 1
j -= 1
elif op == 'D':
ops.append(('D', i-1))
i -= 1
elif op == 'I':
ops.append(('I', j-1))
j -= 1
ops.reverse()
return dp[n][m], ops
不可以使用状态压缩。否则会丢失路径信息。
带权编辑距离#
只要替换操作代价就可以了
def weighted_edit_distance(A, B, insert_cost=1, delete_cost=1, replace_cost=2):
n, m = len(A), len(B)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = i * delete_cost
for j in range(m+1):
dp[0][j] = j * insert_cost
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[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
)
return dp[n][m]
Damerau-Levenshtein 距离（DL 距离）#
在编辑距离的基础上，多出一种操作：能够交换两个相邻的字符
使用动态规划思想来做。
: 表示将 转换为 的最小操作数。
状态转换方程
1. 如果 A[i-1] == B[j-1]：
dp[i][j] = dp[i-1][j-1] （字符相同，无需操作）
2. 否则：
dp[i][j] = min(
dp[i-1][j] + 1, （删除）
dp[i][j-1] + 1, （插入）
dp[i-1][j-1] + 1 （替换）
)
3. 若满足交换条件：
A[i-1] == B[j-2] 且 A[i-2] == B[j-1]
则允许：
dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1) （交换）
伪码（交换操作）
for i in range(1, n+1):
for j in range(1, m+1):
cost = 0 if A[i-1] == B[j-1] else 1
dp[i][j] = min(
dp[i-1][j] + 1, # 删除
dp[i][j-1] + 1, # 插入
dp[i-1][j-1] + cost # 替换或匹配
)
# 检查是否可以交换相邻字符
if i > 1 and j > 1 and A[i-1] == B[j-2] and A[i-2] == B[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1) # 交换