编辑距离（Levenshtein）
推导插入、删除和替换操作的编辑距离递推式，并为不同长度的字符串对填充 DP 表。
编辑距离（Levenshtein） 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
编辑距离问题
编辑距离（莱文斯坦距离，LeetCode 72）要解决的问题是：将一个字符串转换为另一个字符串，所需的插入、删除或替换操作的最少次数是多少？例如，要将 'horse' 转换为 'ros'：将 'h'→'r'（horse→rorse），删除 'r'（rorse→rose），删除 'e'（rose→ros），共需 3 次操作。编辑距离是拼写检查器、DNA 比对和模糊匹配的基础。
# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)
# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose (delete r at index 1)
# 3. rose → ros (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')DP 状态与递推关系
定义 dp[i][j] = word1[:i] 与 word2[:j] 之间的最小编辑距离。如果 word1[i-1] == word2[j-1]，则不需要操作：dp[i][j] = dp[i-1][j-1]。否则，从三种操作中取最小值：插入 dp[i][j-1] + 1、删除 dp[i-1][j] + 1、替换 dp[i-1][j-1] + 1。基本情况：dp[i][0] = i（删除 word1 的全部字符），以及 dp[0][j] = j（插入 word2 的全部字符）。
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
# Base cases
for i in range(m+1): dp[i][0] = i # delete all of word1
for j in range(n+1): dp[0][j] = j # insert all of word2
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] # no cost
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1] # replace
)
return dp[m][n]
print(edit_distance('horse', 'ros')) # 3
print(edit_distance('intention', 'execution')) # 5理解三种操作
这三种操作直接对应 DP 表中的移动：替换 dp[i-1][j-1]+1——两个字符已经匹配，但需要付出一次操作代价。从 word1 中删除 dp[i-1][j]+1——从 word1 中移除一个字符（在表中向上移动）。向 word1 中插入 dp[i][j-1]+1——插入一个字符以匹配 word2（向左移动）。三者中的最小值给出了最优编辑路径。
# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]
word1, word2 = 'cat', 'cut'
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]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
print(' ', ' '.join(' '+word2))
for i, row in enumerate(dp):
print((' ' if i==0 else word1[i-1]), row)空间优化至 O(n)
编辑距离只需要当前行和上一行。使用大小为 n+1 的一维数组，并在更新每个单元格前单独记录 diagonal 值（dp[i-1][j-1]）。从左到右处理：temp = dp[j]（旧值 = dp[i-1][j]），然后使用 dp[j]（删除）、dp[j-1]（插入）和 diagonal（替换）更新 dp[j]。
def edit_distance_1d(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # initial row: 0,1,2,...,n
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j] before overwrite
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], # delete
dp[j-1], # insert
diag) # replace
diag = temp
return dp[n]
print(edit_distance_1d('horse', 'ros')) # 3
print(edit_distance_1d('intention', 'execution')) # 5重建编辑操作
要重建实际的编辑操作序列，请从 (m, n) 开始沿 DP 表回溯。在每个单元格处：如果 word1[i-1] == word2[j-1]，就沿对角线移动（不执行操作）。否则，找出三个相邻单元格中产生最小值的那个，并记录对应的操作。这样得到的编辑脚本是逆序的；请将其反转以得到最终答案。
def edit_ops(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]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
ops, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and word1[i-1]==word2[j-1]:
i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
else:
ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
return list(reversed(ops))
for op in edit_ops('horse', 'ros'): print(op)一次编辑距离检查
一个更简单的面试问题是：两个字符串是否恰好相差一次编辑？无需 DP 即可在 O(n) 时间内解决。让两个字符串同步向前遍历。遇到不匹配时，尝试三种操作（跳过 s1 中的一个字符、跳过 s2 中的一个字符、同时跳过两个字符），并检查剩余部分是否相同。如果出现两次不匹配，返回假值。当您只需要判断距离是否 ≤ 1 时，这种贪心方法可以避免完整的 O(mn) DP。
def is_one_edit_distance(s, t):
m, n = len(s), len(t)
if abs(m - n) > 1: return False
if m > n: return is_one_edit_distance(t, s) # ensure m <= n
for i in range(m):
if s[i] != t[i]:
if m == n:
return s[i+1:] == t[i+1:] # replace
else:
return s[i:] == t[i+1:] # insert into s (delete from t)
return m + 1 == n # all matched, lengths differ by 1
print(is_one_edit_distance('ab', 'acb')) # True (insert c)
print(is_one_edit_distance('ab', 'ab')) # False (zero edits)
print(is_one_edit_distance('ab', 'abc')) # True (append c)
print(is_one_edit_distance('ab', 'xyz')) # False编辑距离与 LCS 的比较
编辑距离（包含三种操作）和 LCS 是观察字符串相似性的互补视角。编辑距离计算差异，LCS 计算相似性。当只允许插入和删除（不允许替换）时，编辑距离 = m + n - 2×LCS。允许替换时，DP 略有不同：匹配时对角线贡献 dp[i-1][j-1]（免费），替换时贡献 dp[i-1][j-1]+1。两种算法的时间复杂度都是 O(mn)。
def lcs_len(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return dp[m][n]
def edit_insert_delete_only(s1, s2):
return len(s1) + len(s2) - 2 * lcs_len(s1, s2)
print(edit_insert_delete_only('sea', 'eat')) # 2
print(edit_distance('sea', 'eat')) # 2 (same here: replace not needed)模糊字符串匹配
编辑距离为现实世界中的模糊匹配提供了核心支持。拼写检查器会建议与输入单词的编辑距离为 1 或 2 以内的更正结果。大规模应用的挑战在于避免进行 O(mn × 字典大小) 次比较。解决方案包括BK 树（用于编辑距离的度量树）、n 元组索引，以及 Bitap 等近似字符串匹配算法。理解底层 DP 有助于您分析这些更高层工具的效率。
def spell_suggest(typed, dictionary, max_dist=2):
'''Return words in dictionary within max_dist edits of typed.'''
suggestions = []
for word in dictionary:
if abs(len(typed) - len(word)) <= max_dist:
if edit_distance(typed, word) <= max_dist:
suggestions.append(word)
return suggestions
def edit_distance(w1, w2):
dp = list(range(len(w2)+1))
for i,c1 in enumerate(w1,1):
prev = i
for j,c2 in enumerate(w2,1):
temp = dp[j]
dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
prev = temp
return dp[len(w2)]
dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary)) # horse, worse, house, morse加权编辑距离
在某些应用中，不同操作具有不同的代价。例如，转置相邻字符（常见的拼写错误）的代价可能低于完整替换。达梅劳–莱文斯坦距离将转置作为第四种操作加入其中。DP 扩展为：当 word1[i-1]==word2[j-2] 且 word1[i-2]==word2[j-1] 时，还要检查 dp[i-2][j-2]+1。这能更准确地模拟键盘输入错误。
def damerau_levenshtein(s, t):
m, n = len(s), len(t)
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):
cost = 0 if s[i-1]==t[j-1] else 1
dp[i][j] = min(
dp[i-1][j]+1, # delete
dp[i][j-1]+1, # insert
dp[i-1][j-1]+cost # replace
)
# Transposition
if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
return dp[m][n]
print(damerau_levenshtein('CA', 'ABC')) # 2
print(damerau_levenshtein('ab', 'ba')) # 1 (transposition)DNA 序列比对
生物信息学使用编辑距离的变体进行DNA 序列比对。尼德尔曼–翁施算法是一种与 LCS 和编辑距离密切相关的全局比对 DP，其中匹配得分为 +1，不匹配得分为 -1，间隙（插入/删除）会产生惩罚。史密斯–沃特曼变体执行局部比对（找出匹配度最高的子串）。两者都是 O(mn) 的 DP 算法，并采用相同的填表结构。
def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
m, n = len(seq1), len(seq2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i * gap
for j in range(n+1): dp[0][j] = j * gap
for i in range(1,m+1):
for j in range(1,n+1):
score = match if seq1[i-1]==seq2[j-1] else mismatch
dp[i][j] = max(
dp[i-1][j-1] + score, # align
dp[i-1][j] + gap, # gap in seq2
dp[i][j-1] + gap # gap in seq1
)
return dp[m][n]
print(needleman_wunsch('GATTACA', 'GCATGCU')) # alignment score编辑距离的面试解题方法
面试中遇到编辑距离问题时：(1) 确认允许的操作（插入/删除/替换）。(2) 清楚定义 DP 状态。(3) 明确写出三种情况和递推关系。(4) 说明基本情况：dp[i][0]=i 和 dp[0][j]=j。(5) 提及 O(n) 空间优化。(6) 如果时间允许，用类似 'cat'→'cut'（1 次替换）的小例子进行推演验证。O(mn) 的时间复杂度，以及 O(mn) → O(n) 的空间复杂度，是标准的复杂度界限。
# Clean interview solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
# O(n) space with rolling row
dp = list(range(n + 1))
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], dp[j-1], diag)
diag = temp
return dp[n]
# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros')) # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc')) # 3
print(min_distance('abc', '')) # 3快速检查
测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：编辑距离 dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost)，其中匹配时 cost=0，否则为 1；基本情况 dp[i][0]=i 和 dp[0][j]=j 表示与空字符串之间的转换；以及O(n) 空间优化使用带有对角线变量的滚动一维数组。接下来我们将应用相同的滚动数组技巧，把二维 DP 表的空间复杂度从 O(mn) 降至 O(min(m,n))。
常见问题解答
「编辑距离（Levenshtein）」课时是免费的吗？
是的 — 「编辑距离（Levenshtein）」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「编辑距离（Levenshtein）」这节课中我会学到什么？
推导插入、删除和替换操作的编辑距离递推式，并为不同长度的字符串对填充 DP 表。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「编辑距离（Levenshtein）」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 网格中的不同路径与最小路径和
- 最长公共子序列
- 编辑距离（Levenshtein）
- 二维 DP 的空间优化