Edit Distance
给你两个单词，word1 和 word2。一次编辑可以通过以下三种方式之一更改 word1：在任意位置插入一个字母、删除一个字母，或将一个字母替换为另一个字母。返回将 word1 变成 word2 所需的最少编辑次数。
函数
- word1string
- 你编辑的单词
- word2string
- 要到达的单词
- 返回值integer
- 将 word1 转换为 word2 所需的最少插入、删除和替换次数
约束条件
1 ≤ word1.length ≤ 5001 ≤ word2.length ≤ 500- 这两个单词只包含小写英文字母。
示例
- 输入
- word1 = "spot"word2 = "stop"
- 输出
- 2
- 解释
- 把 p 换成 t，再把 t 换成 p：
spot变成stot，然后变成stop。一次编辑不够，因为这两个单词有两处不同，而且插入或删除都会改变长度。
- 输入
- word1 = "garden"word2 = "ardent"
- 输出
- 2
- 解释
- 删除字母 g，得到
arden，然后在末尾插入 t，得到ardent。逐个字母替换需要 6 次，因为这两个单词在每个位置上的字母都不同。
- 输入
- word1 = "rain"word2 = "shine"
- 输出
- 3
- 解释
- 把 r 替换成 s，把 a 替换成 h，然后插入 e。两次编辑无法完成：
shine中没有 r 和 a，因此每次都需要进行一次不改变长度的编辑，而且这个单词最终还必须增加一个字母。
进阶
你还能在返回编辑次数的同时，返回一个最短的编辑列表吗？
提示
逐个打开提示，每个都会多透露一点。
看看每个单词的最后一个字母。如果它们相同，你需要修改它们吗？如果它们不同，哪些编辑可以让这两个单词以相同的字母结尾？
对于不同的末尾字母，有三种选择：用一个替换另一个，删除
word1的最后一个字母，或插入word2的最后一个字母。每种选择都会在更短的前缀上留下相同的问题，所以选成本最低的那个，再加 1。在表格中存储每对前缀长度
(i, j)对应的答案。空前缀的代价是删除i次或插入j次，这样就填好了第一行和第一列。逐行填入其余单元格，然后从最后一个单元格读取答案。
题解
编辑之间会相互影响：garden 和 ardent 的 6 个位置都不同，但只需两次编辑。因此，看看每个单词的最后一个字母。要么两个字母相同，要么通过三种编辑操作之一让它们相同，而每种选择都会在更短的前缀上留下同样的问题。用一张表就能一次性解决每一对前缀。
尝试用递归完成这三处编辑
结果正确，但无法在最大的测试中运行完毕
思路
设 edits(i, j) 表示把后缀 word1[i:] 转换成 word2[j:] 所需的最少编辑次数。如果首字母相同，就保留它们并同时移动两个索引：在相同的字母上花费一次编辑永远没有帮助。否则，取以下三种调用中的最小值再加 1：替换会同时移动两个索引，删除 word1[i] 会移动 i，插入 word2[j] 会移动 j。当一个单词用完时，另一个单词中剩下的每个字母都需要一次编辑。
每次不匹配都会产生三次调用：两个各有 15 个字母且没有共同字母的单词，大约需要 6.7 × 10^10 次调用。然而，不同的索引对 (i, j) 只有 (n+1) × (m+1) 个，因此几乎每次调用都会重复之前的调用。
算法
- 如果
i超出word1的末尾，返回m - j；如果j超出word2的末尾，返回n - i。 - 如果
word1[i] == word2[j]，返回edits(i+1, j+1)。 - 否则返回
1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1))。 - 答案是
edits(0, 0)。
def minDistance(word1, word2):
n, m = len(word1), len(word2)
def edits(i, j):
# Fewest edits to turn word1[i:] into word2[j:]
if i == n:
return m - j # insert the rest of word2
if j == m:
return n - i # delete the rest of word1
if word1[i] == word2[j]:
return edits(i + 1, j + 1)
return 1 + min(edits(i + 1, j + 1), # replace word1[i] with word2[j]
edits(i + 1, j), # delete word1[i]
edits(i, j + 1)) # insert word2[j]
return edits(0, 0)填写前缀表
思路
令 dp[i][j] 表示将 word1 的前 i 个字母转换为 word2 的前 j 个字母所需的最少编辑次数。如果 word1[i-1] 等于 word2[j-1]，就复制对角线上的 dp[i-1][j-1]。否则，付出 1 加上相邻单元格中的最小值：对角线表示替换，上方的单元格表示删除 word1[i-1]，左侧的单元格表示插入 word2[j-1]。初始行和列不是 0：将 i 个字母变为空需要删除 i 次，所以 dp[i][0] = i，同理 dp[0][j] = j。
将 spot 转换为 stop 时，最后一行是 [4, 3, 2, 2, 2]。最后一个单元格比较 t 和 p；它的对角线（将 spo 转换为 sto）是 1，其他相邻单元格都是 2，所以答案是 1 + 1 = 2。两个长度为 500 的单词会填充 2.5 × 10^5 个单元格，每个单元格都能在常数时间内计算。
算法
- 创建一个包含
(n+1) × (m+1)个单元格的dp，设置dp[i][0] = i和dp[0][j] = j。 - 当
i从 1 到n、j从 1 到m时：如果word1[i-1] == word2[j-1]，则设置dp[i][j] = dp[i-1][j-1]。 - 否则，设置
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。 - 返回
dp[n][m]。
def minDistance(word1, word2):
n, m = len(word1), len(word2)
# dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i # delete all i letters
for j in range(m + 1):
dp[0][j] = j # insert all j letters
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete word1[i-1]
dp[i][j - 1]) # insert word2[j-1]
return dp[n][m]只保留两行
思路
第 i 行只读取第 i-1 行和本行左侧的单元格，因此只需要两个数组：prev 表示已完成的行，cur 表示正在填充的行。左上方的值是 prev[j-1]，上方的是 prev[j]，左侧的是 cur[j-1]。现在每行的第一个元素就是基础列的值，因此在填充第 i 行之前，先设置 cur[0] = i。
将 word2 转换为 word1 所需的编辑次数相同，因为插入和删除可以互换。交换这两个单词，让各行沿着较短的单词展开：每行只需要 min(n, m) + 1 个数字，而不必使用最多有 251,001 个单元格的表格，工作量仍为 O(n × m)。
算法
- 如果
word2比word1长，就交换它们。 - 设置
prev = [0, 1, ..., m]。 - 对于从 1 到
n的每个i，设置cur[0] = i，并按照表格规则填充cur[1..m]：从prev读取对角线和上方的值，从cur读取左侧的值。然后交换prev和cur。 - 返回
prev[m]。
def minDistance(word1, word2):
if len(word2) > len(word1):
word1, word2 = word2, word1 # the rows run along the shorter word
m = len(word2)
# prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
prev = list(range(m + 1))
for i in range(1, len(word1) + 1):
cur = [i] + [0] * m # i letters into an empty prefix: delete them all
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete word1[i-1]
cur[j - 1]) # insert word2[j-1]
prev = cur
return prev[m]
易错点和边界情况
- 像最长公共子序列那样，用零填充第 0 行和第 0 列。将
abc转为空前缀需要 3 次删除，而不是 0 次。 - 在双行版本中忘记写
cur[0] = i。第一个条目会保留两行之前的值，之后的每个单元格都会出错。 - 匹配时仍然计算一次编辑。对于相同的字母，如果使用
1 + min(...)，将a转成a的代价就是 1。 - 从
prev而不是cur读取左侧邻居。左侧是当前行中插入word2[j-1]的结果。 - 在 Python 中对 500 个字母的单词使用记忆化递归。调用深度会达到 1000，超过默认的递归限制。
常见问题3
编辑距离的时间复杂度是多少？
表格解法会为每对前缀填充一个单元格，耗时为常数时间：对于长度为 n 和 m 的字符串，时间复杂度为 O(n × m)。完整表格需要 O(n × m) 的内存，使用两行则只需 O(min(n, m))。不使用表格的纯递归算法具有指数级时间复杂度。
编辑距离和 Levenshtein 距离是一样的吗？
这个版本是 Levenshtein 距离：插入、删除和替换的代价都为 1。编辑距离是这类算法的统称。只有插入和删除时，结果为 n + m - 2 × LCS；长度相等时只有替换，结果为汉明距离；如果再加入交换两个相邻字母的操作，就是 Damerau 版本。
编辑距离可以用单个数组解决吗？
是的。原地从左向右填充一个数组 row。覆盖 row[j] 之前，它仍保存着上一行的值，而 row[j-1] 已经保存了当前行的值。只有对角线上的值会丢失，所以要把旧的 row[j] 保存到一个变量中，并将它用作 j + 1 的对角线值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def minDistance(word1, word2):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
word1 = "spot" word2 = "stop"
预期输出
2