1、题目
给你两个单词 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由小写英文字母组成
2、思路
(动态规划) O ( n ? m ) O(n * m) O(n?m)
给你两个单词 word1 和 word2，我们可以对一个单词进行插入一个字符，删除一个字符，替换一个字符三种操作，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
样例：
如样例所示，word1 = "horse", word2 = "ros"，我们将word1转换成word2所使用的最少操作数为3，下面来讲解动态规划的做法。
对于动态规划的题目来说，我们一般要考虑两个问题，分别是状态表示和状态计算。状态表示往往和题目的问题相关，因此我们可以定义如下状态表示。
状态表示： f[i][j] 表示将 word1 的前 i 个字符变成 word2 的前 j 个字符所需要进行的最少操作次数。假设word1长度为n，word2长度为m，那么f[n][m]就表示将 word1 的前 n 个字符变成 word2 的前 m 个字符所需要进行的最少操作次数，即为答案。
有了状态表示以后，我们去进行状态计算，推导状态计算方程。
状态计算：
如何计算f[i][j]？考虑word1的第i个字符与word2的第j个字符，分为两种情况：
- 1、
word1[i] == word2[j]，则f[i][j] == f[i - 1][j - 1]; - 2、
word1[i] != word2[j]，我们有三种选择，替换、删除、插入：- 替换： 替换
word1的第i个字符或者替换word2的第j个字符，则f[i][j] == f[i - 1][j - 1] + 1； - 删除： 删除
word1的第i个字符或者删除word2的第j个字符，则f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1; - 插入: 在
word2[j]后面添加word1[i]或者在word1[i]后添加word2[j]，则f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
- 替换： 替换
我们去解释一下上述状态计算：
当word1[i] == word2[j]时，当前两个字符相同，我们不需要做任何操作，此时f[i][j]就可以从f[i - 1][j - 1]的状态转移过来，换句话说，此时f[i][j]的状态取决于f[i - 1][j - 1]。
当word1[i] != word2[j]时，此时我们可以进行的操作有三种：
- 替换： 替换
word1的第i个字符或者替换word2的第j个字符，当前位置的字符不匹配，进行替换操作后两者变得相同。
所以f[i][j] == f[i - 1][j - 1] + 1。
-
删除： 删除
word1的第i个字符或者删除word2的第j个字符。如果当前
word1[0 ~ i-1]与word2[0 ~ j]匹配，我们删除多余的word1[i]，或者word1[0 ~ i]与word2[0 ~ j-1]匹配，我们删除多余的word[j]。
两种情况的状态分别为f[i - 1][j]和f[i][j - 1]，因为题目要求最少操作数，故二者之间我们取一个最小值，所以f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1。 -
插入: 在
word2[j]后面添加word1[i]或者在word1[i]后添加word2[j]。如果当前
word1[0 ~ i-1]与word2[0 ~ j]匹配或者word1[0 ~ i]与word2[0 ~ j-1]匹配，除了考虑删除多余的字符操作以外，我们还可以执行添加操作，因此添加和删除的状态计算其实是一样的。
所以
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1。
考虑完状态计算和状态转移以后，接下来我们去进行状态初始化。
3、初始化
for(int i = 0; i <= n; i++) f[i][0] = i; //将长度为i的word1变成长度为0的word2需要进行最少i次删除操作
for(int i = 0; i <= m; i++) f[0][i] = i; //将长度为i的word2变成长度为0的word1需要进行最少i次删除操作
实现细节：
其实我们可以注意到，word[]数组下标如果从1开始的话，第i个字符就是word[i]，而不是下标从0开始的word[i - 1]，这样的word[]数组与我们的状态表示会更加相对应。因此，为了代码的可读性更高，我们给word1[]数组和word2[]数组的开头都去添加一个空格，然后在状态计算时，下标从1开始。
时间复杂度分析： 状态数为 O ( n ? m ) O(n * m) O(n?m)，状态计算为 O ( 1 ) O(1) O(1)，因此总的时间复杂度为 O ( n ? m ) O(n * m) O(n?m)。
4、c++代码
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
word1 = ' ' + word1; //添加空格
word2 = ' ' + word2;
vector<vector<int>>f(n + 1, vector<int>(m + 1));
for(int i = 0; i <= n; i++) f[i][0] = i; //i次删除
for(int i = 0; i <= m; i++) f[0][i] = i; //i次删除 word1 -> word2
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1; //添加或者删除
if(word1[i] == word2[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); //替换
}
return f[n][m];
}
};
5、Java代码
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length(), m = word2.length();
word1 = ' ' + word1; //添加空格
word2 = ' ' + word2;
int[][] f = new int[n + 10][m + 10];
for(int i = 0;i <= n;i++) f[i][0] = i; //i次删除
for(int i = 0;i <= m;i++) f[0][i] = i; //i次删除 word1 -> word2
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1); //添加或者删除
if(word1.charAt(i) == word2.charAt(j)) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);//替换
}
return f[n][m];
}
}
原题链接： 72. 编辑距离
