*************
C++
*************
看一下题目
想到了小时候暑假的某天下午，阳光热烈，老师在讲台上讲课，粉笔灰在透过窗台的阳光中慢慢的降落，我顾不上那一刻的达尔文效应，我在冥思苦想汉诺塔，虽然跟这个没啥关系，但是就是突然想起来这个场景。为什么人在回忆自己的事情的时候是第三视角，而不是第一视角呢？
首先，矩阵的起手式已经非常的成熟了, 先数出来两个单词的长度m 和 n，这个用于构建矩阵，然后把矩阵初始化为0，之后填充第一行第一列，这步很快，无他，唯手熟尔。
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));
// initialise the first column
for (int i = 0; i <= m; ++i) {
dp[i][0] = i;
}
// initialise the first row
for (int j = 0; j <= n; ++j) {
dp[0][j] = j;
}
}
};其次，举例美学：
word1 = else; word2 = where
初始化这个过程比较简单，就是
第一列 dp[i][0] = i，表示将 word1 的前 i 个字符转换为空字符串需要 i 次删除操作。
第一行 dp[0][j] = i，表示将 word2 的前 j 个字符转换为空字符串需要 j 次删除操作。
|
| w | h | e | r | e | |
| 0 | 1 | 2 | 3 | 4 | 5 | |
| e | 1 | |||||
| l | 2 | |||||
| s | 3 | |||||
| e | 4 | |||||
完美的矩阵，接下来就是填充剩下的矩阵了，涉及到元素的替换只有三种方式，删除，插入和替换。假设我是计算机，我首先会遍历一下单词的所有元素，每个字母只有三种状态，删除、插入和替换。分别对应下面的公式：
-
dp[i-1][j]：删除word1[i-1] -
dp[i][j-1]：插入word2[j-1] -
dp[i-1][j-1]：替换word1[i-1]为word2[j-1]
填充 dp[1][1]
-
word1[0] = 'e'，word2[0] = 'w'，字符不同。 -
计算
dp[1][1]： -
删除操作：
dp[0][1] = 1，删除字母w -
插入操作：
dp[1][0] = 1，插入字母w -
替换操作：
dp[0][0] = 0，替换字母w
这里选择删除或者插入：
-
删除操作：删除
word1的第一个字符e，使其与word2的第一个字符w匹配。此时，编辑距离为dp[0][1] + 1 = 1 + 1 = 2。 -
插入操作：在
word1的第一个字符e之前插入word2的第一个字符w，使其与word2的第一个字符w匹配。此时，编辑距离为dp[1][0] + 1 = 1 + 1 = 2。 -
替换操作：将
word1的第一个字符e替换为word2的第一个字符w，使其与word2的第一个字符w匹配。此时，编辑距离为dp[0][0] + 1 = 0 + 1 = 1。
最小值是1，所以填充1。至于为什么要 + 1， 我也是想了很久才想起来，本来周五晚上写的，没加注释的话，当时想的是只有我和佛祖知道，等到我再看代码的时候，不禁感慨，完了，只有佛祖知道了。
在每种情况下，加1是为了计算从 word1 的前 i-1 个字符到 word2 的前 j-1 个字符所需的操作次数，再加上当前的编辑操作。
例如，如果我正在计算 dp[1][1] 并且我选择替换操作，我从 dp[0][0]（即0）开始，然后加1来反映替换操作，得到 dp[1][1] = 1。这个1表示将 word1 的第一个字符 'e' 替换为 word2 的第一个字符 'w'，这是将 'e' 转换为 'w' 所需的唯一操作。
更新矩阵：
|
| w | h | e | r | e | |
| 0 | 1 | 2 | 3 | 4 | 5 | |
| e | 1 | 1 | ||||
| l | 2 | |||||
| s | 3 | |||||
| e | 4 | |||||
填充 dp[1][2]
-
word1[0] = 'e'，word2[1] = 'h'，字符不同。
计算 dp[1][2]：
-
删除操作：
dp[0][2] = 2，删除字母h -
插入操作：
dp[1][1] = 1，插入字母h -
替换操作：
dp[0][1] = 1，替换字母h
这里选择删除或者插入：
-
删除操作：删除
word1的第一个字符e，使其与word2的第二个字符h匹配。此时，编辑距离为dp[0][2] + 1 = 2 + 1 = 3。 -
插入操作：在
word1的第一个字符e之前插入word2的第二个字符h，使其与word2的第二个字符h匹配。此时，编辑距离为dp[1][1] + 1 = 1 + 1 = 2。 -
替换操作：将
word1的第一个字符e替换为word2的第二个字符h，使其与word2的第二个字符h匹配。此时，编辑距离为dp[0][1] + 1 = 1 + 1 = 2。
最小值为 1，加一后为 2。
更新矩阵：
|
| w | h | e | r | e | |
| 0 | 1 | 2 | 3 | 4 | 5 | |
| e | 1 | 1 | 2 | |||
| l | 2 | |||||
| s | 3 | |||||
| e | 4 | |||||
填充 dp[1][3]
-
word1[0] = 'e'，word2[2] = 'e'，字符相同。
计算 dp[1][3]：
-
删除操作：
dp[0][3] = 3，删除字母e -
插入操作：
dp[1][2] = 2，插入字母e -
替换操作：
dp[0][2] = 2，替换字母e
这里选择删除或者插入：
-
删除操作：删除
word1的第一个字符e，使其与word2的第三个字符e匹配。此时，编辑距离为dp[0][3] + 1 = 3 + 1 = 4。 -
插入操作：在
word1的第一个字符e之前插入word2的第三个字符e，使其与word2的第三个字符e匹配。此时，编辑距离为dp[1][2] + 1 = 2 + 1 = 3。 -
替换操作：将
word1的第一个字符e替换为word2的第三个字符e，使其与word2的第三个字符e匹配。此时，编辑距离为dp[0][2] + 1 = 2 + 1 = 3。
最小值为 2，加一后为 3。
更新矩阵：
|
| w | h | e | r | e | |
| 0 | 1 | 2 | 3 | 4 | 5 | |
| e | 1 | 1 | 2 | 3 | ||
| l | 2 | |||||
| s | 3 | |||||
| e | 4 | |||||
填充 dp[1][4]
-
word1[0] = 'e'，word2[3] = 'r'，字符不同。
计算 dp[1][4]：
-
删除操作：
dp[0][4] = 4，删除字母r -
插入操作：
dp[1][3] = 2，插入字母r -
替换操作：
dp[0][3] = 3，替换字母r
这里选择删除或者插入：
-
删除操作：删除
word1的第一个字符e，使其与word2的第四个字符r匹配。此时，编辑距离为dp[0][4] + 1 = 4 + 1 = 5。 -
插入操作：在
word1的第一个字符e之前插入word2的第四个字符r，使其与word2的第四个字符r匹配。此时，编辑距离为dp[1][3] + 1 = 2 + 1 = 3。 -
替换操作：将
word1的第一个字符e替换为word2的第四个字符r，使其与word2的第四个字符r匹配。此时，编辑距离为dp[0][3] + 1 = 3 + 1 = 4。 -
更新矩阵
|
| w | h | e | r | e | |
| 0 | 1 | 2 | 3 | 4 | 5 | |
| e | 1 | 1 | 2 | 3 | 3 | |
| l | 2 | |||||
| s | 3 | |||||
| e | 4 | |||||
填充 dp[1][5]
-
word1[0] = 'e'，word2[4] = 'e'，字符相同。
计算 dp[1][5]：
-
删除操作：
dp[0][5] = 5，删除字母e -
插入操作：
dp[1][4] = 3，插入字母e -
替换操作：
dp[0][4] = 4，替换字母e
这里选择删除或者插入：
-
删除操作：删除
word1的第一个字符e，使其与word2的第五个字符e匹配。此时，编辑距离为dp[0][5] + 1 = 5 + 1 = 6。 -
插入操作：在
word1的第一个字符e之前插入word2的第五个字符e，使其与word2的第五个字符e匹配。此时，编辑距离为dp[1][4] + 1 = 3 + 1 = 4。 -
替换操作：将
word1的第一个字符e替换为word2的第五个字符e，使其与word2的第五个字符e匹配。此时，编辑距离为dp[0][4] + 1 = 4 + 1 = 5。 -
更新矩阵
|
| w | h | e | r | e | |
| 0 | 1 | 2 | 3 | 4 | 5 | |
| e | 1 | 1 | 2 | 3 | 3 | 4 |
| l | 2 | |||||
| s | 3 | |||||
| e | 4 | |||||
最后，依次类推：
-
dp[1][1]：替换e为w，操作数为1。 -
dp[1][2]：替换e为h，操作数为2。 -
dp[1][3]：字符相同，不需要操作，操作数为2。 -
dp[1][4]：替换e为r，操作数为3。 -
dp[1][5]：字符相同，不需要操作，操作数为4。 -
dp[2][1]：删除l，操作数为2。 -
dp[2][2]：替换l为h，操作数为2。 -
dp[2][3]：替换l为e，操作数为3。 -
dp[2][4]：替换l为r，操作数为3。 -
dp[2][5]：替换l为e，操作数为4。 -
dp[3][1]：删除s，操作数为3。 -
dp[3][2]：替换s为h，操作数为3。 -
dp[3][3]：替换s为e，操作数为3。 -
dp[3][4]：替换s为r，操作数为4。 -
dp[3][5]：替换s为e，操作数为4。 -
dp[4][1]：删除e，操作数为4。 -
dp[4][2]：替换e为h，操作数为4。 -
dp[4][3]：字符相同，不需要操作，操作数为3。 -
dp[4][4]：替换e为r，操作数为4。 -
dp[4][5]：字符相同，不需要操作，操作数为4。
最终，dp[4][5] 的结果为 4，表示将 word1 = "else" 转换为 word2 = "where" 所需的最小编辑操作数为 4。
OK，原理知道了，代码也就好写了：
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));
// initialise the first column
for (int i = 0; i <= m; ++i) {
dp[i][0] = i;
}
// initialise the first row
for (int j = 0; j <= n; ++j) {
dp[0][j] = j;
}
// fill the dp
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]; // need no cosplay cuz they are same
} else {
dp[i][j] = min({dp[i - 1][j], // delete
dp[i][j - 1], // insert
dp[i - 1][j - 1]}) + 1; // replace
}
}
}
return dp[m][n];
}
};天冷了，注意加衣服。
标签：字符,删除,编辑,word1,短距离,word2,替换,dp From： https://blog.csdn.net/ElseWhereR/article/details/143801406