編輯距離是字串處理中的經典問題，衡量將一個字串變成另一個字串所需的最少操作數。
問題定義#
給定兩個字串 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) # 交換