给你两个单词
word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
示例 2：
提示：
0 <= word1.length, word2.length <= 500
word1和word2由小写英文字母组成
解法一：二维 DP，从后往前填表
无论选择什么操作，最后都会变成一个规模更小的编辑距离问题。
所以，编辑距离天然具有「大问题拆成更小同类问题」的结构。
对于长度为 n 的字符串：
- 可以删除任意位置字符
- 可以插入任意字符
- 可以替换任意字符
每个状态都会产生大量新状态，搜索会反复计算它。快速产生指数级扩张。
而动态规划的核心思想正是：如果一个子问题会被反复求解，那么把答案存下来。
我们可以用一个二维表。表里的每个位置
dp[i][j] 表示：word1[i:] 转换成 word2[j:] 需要的最少操作数。也就是说，当前位置不是只看一个字符，而是看两个字符串从当前位置开始的整个后缀。例如：
word1="horse"， word2="ros"dp[1][1]表示："orse” → "os” 最少需要多少操作。Base Case
其中一个字符串为空时，只能不断插入或删除剩余字符。
- 如果
word1已经用完，但word2还有剩余字符，那只能不断插入。
- 如果
word2已经用完，但word1还有剩余字符，那只能不断删除。
在二维表
dp中，我们需要多一行和多一列，用来处理空字符串。状态转移
- 如果
word1[i] == word2[j]，说明当前字符一样，不需要做任何操作，问题直接缩小为dp[i + 1][j + 1]， 即dp[i][j] = dp[i + 1][j + 1]。
- 如果
word1[i] != word2[j]，说明当前两个字符不一样，我们就在插入、删除、替换三种操作中选代价最小的那个，再加上当前这一步操作。
从右下角开始填表
因为
dp[i][j] 依赖的是右边、下边、右下角这些更靠后的状态，因此必须先计算它们。所以我们要从右下角往左上角倒着填表。
最终
dp[0][0] 就是整个问题的答案。建表示例
word1="horse"， word2="ros"行表示
word1 的后缀起点， 列表示 word2 的后缀起点，再额外加一行一列表示空字符串：填 Base Case
- 最后一行表示："" → word2[j:], 只能插入。
- 最后一列表示：word1[i:] → "", 只能删除。
从右下角开始推, 最终整张表会变成：
dp[0][0] 表示 "horse” → "ros” 整个问题的答案。
horse
rorse (h -> r)
rose (删除 r)
ros (删除 e)
共 3 步。
复杂度
- 空间复杂度：O(m * n)
DP 表大小是(m + 1) * (n + 1)。
- 时间复杂度：O(m * n)
DP 表的每个状态只计算一次。
其中
m 是 word1 长度，n 是 word2 长度。解法二：二维 DP，从前往后填表
这个写法和解法一的本质完全一样，只是状态定义换了一个方向。
这里的
dp[i][j] 表示：word1[:i] 转换成 word2[:j] 需要的最少操作数。也就是把两个字符串的前缀拿出来比较。
这种写法更常见，因为表格从左上往右下填，很多人理解起来更自然。
复杂度分析
- 时间复杂度：O(m * n)
- 空间复杂度：O(m * n)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-72-编辑距离
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 79] 单词搜索
下一篇
[Leetcode 83] 删除排序链表中的重复元素