给你两个单词 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 < = w o r d 1. l e n g t h , w o r d 2. l e n g t h < = 500 0 <= word1.length, word2.length <= 500 0<=word1.length,word2.length<=500
- word1 和 word2 由小写英文字母组成
思路：动态规划
-
字符串 word1 的长度为 n，word2 的长度 为 m
-
定义 f[i][j] 为将字符串 word1[1…i] 转换为 word[2…j] 所需要的最少操作次数
-
初始时，需要在 word1 和 word2 前面塞一个不存在的 字符，使得下标可以从 1 开始，这样后面就不需要做特殊判断
- j = 0时，f[i][0] 表示将字符串 word[1…i] 转换为空字符串需要的最短操作次数，显然，可以删除所有字符，使其变为空，所以操作次数 f[i][0] = i
- i = 0时，f[0][j] 表示将字符串 空字符串 转换为 word2[1…j] 需要的最短操作次数，显然，可以每次添加一个字符，使其变为word[1…j]，所以操作次数 f[0][j] = j
-
f[i][j] 的状态转移方程可以进行如下定义：
- 如果 word1[i] == word[j]，说明它们的最后一个字符相等，不用任何操作，则 f[i][j] = f[i-1][j-1]，如果 word1[i] != word[j]，则需要修改word1[i] 的最后一个字符 f[i][j] = f[i-1][j-1] + 1
- 如果 word1[i] -> word2[j] 需要添加一个字符，则说明 word1[1…i] == word2[1…j-1] 则 f[i][j-1] + 1
- 如果 word1[i] -> word2[j] 需要删除一个字符，则说明 word1[1…i-1] == word2[1…j] 则 f[i-1][j] + 1
-
所以最终 f[i][j] 取上面几种情况的最小值即可，则有
f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
f[i][j] = min(f[i][j], f[i-1][j-1] + (word1[i] != word2[j]));
class Solution {
public:
int f[510][510];
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
word1 = "#" + word1, word2 = "#" + word2;
memset(f, 0x3f, sizeof f);
for(int i = 0; i <= n; i++) f[i][0] = i;
for(int j = 0; j <= m; j++) f[0][j] = j;
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;
f[i][j] = min(f[i][j], f[i-1][j-1] + (word1[i] != word2[j]));
}
}
return f[n][m];
}
};