1.题目
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
示例：
输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')
链接：https://leetcode.cn/problems/edit-distance/description/
2.分析
??可以转化为一道多维的动态规划问题，在两个字符串的删除操作的基础上添加了删除和替换操作。我们可以在二维的基础上额外添加一个变量来表示操作类型
??k = 0，删除操作，k = 1替换操作，k = 2插入操作
1.确定dp数组
??dp[i][j][k] 表示在word1 [0..i] ，word2 [0..j] 的子串执行k操作后满足两个字符串相等的最小操作数，k = 0,1,2
??例如：
? word1 = "h" ， word2 = "r"，dp[1][1][0] 表示执行删除操作后，word1 和 word2 相等的最小操作数，显然 dp[1][1][0] = 2
? 要记住 k 操作对应的是最后一个操作
??在使用动态规划的时候，在清晰 dp[i][j]考虑的是 i，j是末尾的状态的值，不要去考虑对别的值的影响，例如 dp[k][p] (k ≥ i 和 p≥ j的情况)
2.确定转换公式
转换可以分为两个情况， word1[i] == word2[j] 和 word1[i] ≠ word2[j]
1.word1[i] == word2[j]
如果 word1[i] == word2[j]了，那么我们其实不需要进行任何操作，此时取前一个状态的最小值就好
int tmp = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]), dp[i - 1][j - 1][2]);dp[i][j][0] = tmp;dp[i][j][1] = tmp;dp[i][j][2] = tmp;
2.word1[i] ≠ word2[j]
word1[i] ≠ word2[j]时，可以拆分为插入，删除和替换三种情况
2.1 删除
??删除操作对应dp[i][j]时删除 i 或者 删除 j，那么只要考虑 dp[i-1][j]，dp[i][j-1]的情况即可（注意这里 dp[i-1][j]，dp[i][j-1] 都可能进行多种操作）
int tmp2 = min(min(dp[i - 1][j][1], dp[i - 1][j][2]), dp[i - 1][j][0]);int tmp3 = min(min(dp[i][j-1][1], dp[i][j-1][2]), dp[i][j-1][0]);dp[i][j][0] = min(tmp2, tmp3) + 1;
2.2 替换
对于[i][j]进行替换，那么我们只需要替换 i 或者 替换 j 就可以了，替换就是在 [0..i-1] [0..j-1]的基础上，加上一个操作使得 i == j
int tmp1 = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]), dp[i - 1][j - 1][2]); dp[i][j][1] = tmp1 + 1;
2.3 插入
对于插入操作，本质和删除一致的，为什么这么说呢？
??word1[i] ≠ word2[j]，我们只能在 i 或者 j 的尾部进行插入，即 i-1 插入字符 char 使得 char == word2[j]；或者 j-1 位置插入字符 char 使得 char == word1[i]
??如果在 i 或者 j后面插入，我们还需要额外进行一次删除操作，因此插入操作代码和删除一致，这里可以进行优化
int tmp2 = min(min(dp[i - 1][j][1], dp[i - 1][j][2]), dp[i - 1][j][0]);int tmp3 = min(min(dp[i][j-1][1], dp[i][j-1][2]), dp[i][j-1][0]);dp[i][j][2] = min(tmp2, tmp3) + 1;
3. 初始化
考虑到dp会用到前面的数据，便于递推额外添加一个大小，因此 dp初始化为 vector<vector<vector<int>>> dp(word1.size() + 1, vector<vector<int>>(word2.size()+ 1, vector<int>(3)));
??word1取[0..0]的时候，word1为空字符串“”；word2只能删除全部字符，或者word2替换全部字符为 " " 空字符串，或者word1插入和word2一样的字符
??同理word2取[0..0]的时候也是
vector<vector<vector<int>>> dp(M + 1, vector<vector<int>>(N + 1, vector<int>(3))); //每一步都可能执行不同的操作 这时候替换表示地替换成 "" 空字符串，插入表示对另一边进行插入 for (int i = 0; i <= M; ++i) { dp[i][0][0] = i; dp[i][0][1] = i; dp[i][0][2] = i; } for (int j = 0; j <= N; ++j) { dp[0][j][0] = j; dp[0][j][1] = j; dp[0][j][2] = j; }
3. 代码实现
class Solution {public: int minDistance(string word1, string word2) { //dp[i][j][k] 表示 [0..i] [0..j]相同所需的最少操作符 k表示执行这个操作时最小值 //最后只需要对三个数 求最小值 const int M = word1.size(); const int N = word2.size(); vector<vector<vector<int>>> dp(M + 1, vector<vector<int>>(N + 1, vector<int>(3))); //每一步都可能执行不同的操作 这时候替换表示地替换成 "" 空字符串，插入表示对另一边进行插入 // 0-插入 1 -删除 2-替换 for (int i = 0; i <= M; ++i) { dp[i][0][0] = i; dp[i][0][1] = i; dp[i][0][2] = i; } for (int j = 0; j <= N; ++j) { dp[0][j][0] = j; dp[0][j][1] = j; dp[0][j][2] = j; } for (int i = 1; i <= M; ++i) { for (int j = 1; j <= N; ++j) { if (word1[i-1] == word2[j-1]) { int tmp = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]), dp[i - 1][j - 1][2]); dp[i][j][0] = tmp; dp[i][j][1] = tmp; dp[i][j][2] = tmp; } else { int tmp2 = min(min(dp[i - 1][j][1], dp[i - 1][j][2]), dp[i - 1][j][0]); int tmp3 = min(min(dp[i][j-1][1], dp[i][j-1][2]), dp[i][j-1][0]); dp[i][j][0] = min(tmp2, tmp3) + 1; //替换 在i-1,j-1的基础上，替换值 int tmp1 = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]), dp[i - 1][j - 1][2]); dp[i][j][1] = tmp1 + 1; //插入 - 最优情况只能在少的一边插入，否则会增加一个删除操作 //删除和插入本质应该一致，因为都应该在尾部插，否则增加额外一个删除操作 dp[i][j][2] = dp[i][j][0]; } } } return min(min(dp[M][N][0], dp[M][N][1]), dp[M][N][2]); }};
经验首页