编辑距离
给你两个单词 word1 和 word2。
请返回将 word1 转换成 word2 所使用的最少操作数。
可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse 将 'h' 替换为 'r'
rorse -> rose 删除 'r'
rose -> ros 删除 'e'
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention 删除 't'
inention -> enention 将 'i' 替换为 'e'
enention -> exention 将 'n' 替换为 'x'
exention -> exection 将 'n' 替换为 'c'
exection -> execution 插入 'u'
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
解法一（二维动态规划）：
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; i++)
{
dp[i][0] = i;
}
for (int j = 0; j <= n; j++)
{
dp[0][j] = j;
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (word1[i - 1] == word2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1];
}
else
{
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
}
}
}
return dp[m][n];
}
};
解法二（一维滚动数组优化）：
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<int> dp(n + 1, 0);
for (int j = 0; j <= n; j++)
{
dp[j] = j;
}
for (int i = 1; i <= m; i++)
{
int prev = dp[0];
dp[0] = i;
for (int j = 1; j <= n; j++)
{
int temp = dp[j];
if (word1[i - 1] == word2[j - 1])
{
dp[j] = prev;
}
else
{
dp[j] = min({dp[j], dp[j - 1], prev}) + 1;
}
prev = temp;
}
}
return dp[n];
}
};
核心思想
这题要求把一个字符串变成另一个字符串的最少操作数。
直接想法是尝试所有操作序列：
- 某一步插入一个字符
- 某一步删除一个字符
- 某一步替换一个字符
但是操作顺序组合非常多，直接搜索会产生大量重复状态。
更适合的做法是用动态规划比较两个字符串的前缀。
这题最关键的观察是：
把
word1的前i个字符变成word2的前j个字符，只依赖更短前缀之间的编辑距离。
因此可以从空前缀开始，逐步计算更长前缀之间的最小编辑距离。
状态定义
定义：
dp[i][j] 表示把 word1 的前 i 个字符，转换成 word2 的前 j 个字符所需要的最少操作数。
也就是：
word1[0...i - 1] -> word2[0...j - 1]
所需的最小编辑距离。
题目要求的答案就是：
dp[m][n]
其中：
m = word1.size()n = word2.size()
递推公式推导
考虑 dp[i][j]。
此时比较的是：
word1的第i个字符：word1[i - 1]word2的第j个字符：word2[j - 1]
1. 两个字符相同
如果：
word1[i - 1] == word2[j - 1]
说明这两个字符不需要额外操作。
只需要把它们前面的部分变成一样：
dp[i][j] = dp[i - 1][j - 1]
2. 两个字符不同
如果：
word1[i - 1] != word2[j - 1]
最后一步操作有三种可能。
删除
先把 word1 的前 i - 1 个字符变成 word2 的前 j 个字符。
然后删除 word1[i - 1]。
对应：
dp[i - 1][j] + 1
插入
先把 word1 的前 i 个字符变成 word2 的前 j - 1 个字符。
然后在末尾插入 word2[j - 1]。
对应：
dp[i][j - 1] + 1
替换
先把 word1 的前 i - 1 个字符变成 word2 的前 j - 1 个字符。
然后把 word1[i - 1] 替换成 word2[j - 1]。
对应：
dp[i - 1][j - 1] + 1
所以取三者最小值：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
代码中写成：
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
边界情况
如果 word2 是空串，那么要把 word1 的前 i 个字符变成空串，只能全部删除。
所以：
dp[i][0] = i
如果 word1 是空串，那么要把空串变成 word2 的前 j 个字符，只能逐个插入。
所以：
dp[0][j] = j
代码中初始化：
for (int i = 0; i <= m; i++)
{
dp[i][0] = i;
}
for (int j = 0; j <= n; j++)
{
dp[0][j] = j;
}
如果两个字符串都为空，dp[0][0] = 0，表示不需要任何操作。
为什么可以按前缀长度递推
计算 dp[i][j] 时，只依赖三个更短或更小的状态：
dp[i - 1][j]dp[i][j - 1]dp[i - 1][j - 1]
如果按 i 从小到大、j 从小到大遍历：
- 上一行状态已经计算完成
- 当前行左侧状态已经计算完成
- 左上角状态也已经计算完成
所以每个状态都可以由已经得到的最优状态推出。
解法二：一维滚动数组优化
二维动态规划中，计算当前行时，只需要用到：
- 上一行同一列：
dp[i - 1][j] - 当前行左一列：
dp[i][j - 1] - 上一行左上角：
dp[i - 1][j - 1]
所以可以用一维数组 dp[j] 保存当前行的状态。
更新时：
- 更新前的
dp[j]表示二维里的dp[i - 1][j] - 更新后的
dp[j - 1]表示二维里的dp[i][j - 1] - 变量
prev表示二维里的dp[i - 1][j - 1]
因此字符相同时：
dp[j] = prev
字符不同时：
dp[j] = min(dp[j], dp[j - 1], prev) + 1
每次更新前用：
int temp = dp[j];
保存旧的上一行同一列。
循环末尾再令：
prev = temp;
这样下一列就能继续使用正确的左上角旧值。
正确性证明
我们证明：动态规划算法返回的结果等于把 word1 转换成 word2 的最少操作数。
结论 1：边界初始化正确
把任意长度为 i 的字符串变成空串，最少需要删除 i 次。
所以 dp[i][0] = i。
把空串变成任意长度为 j 的字符串，最少需要插入 j 次。
所以 dp[0][j] = j。
当两个字符串都是空串时，不需要任何操作，dp[0][0] = 0。
因此边界初始化正确。
结论 2：当最后字符相同时，递推公式正确
如果 word1[i - 1] == word2[j - 1]，最后一个字符已经相同，不需要对它额外操作。
此时只需要把前面的部分：
word1[0...i - 2]
转换成：
word2[0...j - 2]
所以：
dp[i][j] = dp[i - 1][j - 1]
正确。
结论 3：当最后字符不同时，递推公式覆盖了所有最优操作
如果 word1[i - 1] != word2[j - 1]，最后一步操作只可能是三种之一。
如果最后一步是删除，那么之前必须已经完成：
word1[0...i - 2] -> word2[0...j - 1]
代价是 dp[i - 1][j] + 1。
如果最后一步是插入，那么之前必须已经完成：
word1[0...i - 1] -> word2[0...j - 2]
代价是 dp[i][j - 1] + 1。
如果最后一步是替换，那么之前必须已经完成：
word1[0...i - 2] -> word2[0...j - 2]
代价是 dp[i - 1][j - 1] + 1。
任意合法转换序列的最后一步都属于这三种情况之一。
取三者最小值，就不会漏掉最优解，也不会加入非法操作。
因此最后字符不同时的递推正确。
结论 4：计算顺序保证依赖状态已经完成
算法按前缀长度从小到大计算。
当计算 dp[i][j] 时，dp[i - 1][j]、dp[i][j - 1] 和 dp[i - 1][j - 1] 都已经计算完成。
所以每个状态都能由正确的旧状态推出。
结论 5：一维滚动数组与二维动态规划等价
一维数组更新时，dp[j] 在更新前表示上一行同一列，更新后的 dp[j - 1] 表示当前行左一列，prev 表示上一行左上角。
这三个值正好对应二维转移中的删除、插入和替换来源。
因此一维滚动数组只是复用了空间，不会改变计算结果。
得出结论
由结论 1 可知，边界初始化正确。
由结论 2 和结论 3 可知，状态转移正确。
由结论 4 可知，计算顺序正确。
由结论 5 可知，一维优化与二维动态规划等价。
因此算法返回的 dp[m][n] 或 dp[n] 就是最少操作数。
举例理解
以：
word1 = "horse"
word2 = "ros"
为例。
一种最优转换方式是：
horse -> rorse
把 'h' 替换成 'r'。
rorse -> rose
删除第二个字符 'r'。
rose -> ros
删除最后一个字符 'e'。
总共用了 3 次操作。
动态规划会在比较两个字符串前缀时，自动在插入、删除、替换三种操作中选择代价最小的方案。
所以最终：
dp[5][3] = 3
再看：
word1 = ""
word2 = "abc"
只能插入三个字符，所以答案是：
3
这正对应边界状态：
dp[0][3] = 3
复杂度分析
设 m = word1.length，n = word2.length。
解法一
需要计算 (m + 1) * (n + 1) 个状态。
- 时间复杂度：
O(mn) - 空间复杂度：
O(mn)
解法二
同样需要计算每个状态一次。
一维数组长度为 n + 1。
- 时间复杂度：
O(mn) - 空间复杂度：
O(n)
解法二空间更优，是更推荐的写法。