给你两个单词 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 由小写英文字母组成
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
};
此题是一个最短编辑距离问题，我们在工作中用到工具和框架有很多也是类似的算法。比如Git提交，对比差异。vue中将更新前的虚拟dom改成更新后的虚拟dom（vue中对此做了取舍，有优化）
首先对题意要有个理解：
一、分析题意
三种操作，增，删，改，都是针对word1的。但是其实此题目中只要求求出最短操作。所以
word1和word2之间，操作互换一样可以达到同样的效果。
比如word1为people，word2为peopl，此时，word1末尾删除e 或者 word2末尾增加e都可以达到 word1 == word2 的效果。
所以针对word1的增删操作可以转化为对word1或者word2的增操作
再加上对word1的改操作
二、解题思路
假如当word1和word2末尾相同的时候，其实是相当于没有操作。 比如 people 到peopl 和peoplee到people 二者所需要的操作都是相同的。
根据题目意思，我们需要找到最少操作数，最少最优，基本上都和贪心及动态规划有关系。
此题需要对比word1和word2进行对比操作。先使用动态规划解决。
- 首先构建一个二维数组用来记录子问题的解。
| dp | “” | r | (ro) o | (ros) s |
| ------------ | -- | ----- | ---------- | ----------- |
| “” | 0 | 1 | 2 | 3 |
| h | 1 | | | |
| (ho) o | 2 | | | |
| (hor)r | 3 | | | |
| (hors)s | 4 | | | |
| (horse)e | 5 | | | |
dp[i][j] 表示 i 到 j 所需要的步数，以dp[2][1]为例子，表示“ho”转换到“r” 所需要的操作数
如表，是我们要初始化出来的dp二维数组。表内数字，分别代表竖列到达横排所需要的操作数。
有了dp数组，我们先来操作一次。求出dp[1][1]的值。
- dp[1][1]处，
word1为h，word2为r。两位不同,那么有三种处理方式
h -> r 更改h,操作数为1，修改之后变成了 r和r，参照说明中的第二条，我们再加上dp[0][0]即可 word2增加h变为rh,操作数为1, h和rh参照说明中的第二条，就变成了‘’ => "r"所用的步数，dp[0][1] word1增加r变为hr,操作数为1, hr和r参照说明中的第二条，就变成了‘h’ => ""所用的步数，dp[1][0]
- 当我们分析出了以上三种情况后，我们肯定要取最小值作为我们此次dp[1][1]所要求出来的值了。
- 转换为代码就是
1 + Math.min(dp[0][0],dp[0][1],dp[1][0])
- 以上是末尾不相同的情况，如果相同，请参照
说明第二条。实际上就是和横纵各退一步的情况相同
- 最后我们将
dp[i][j]看作此次dp[1][1]时。实际代码就出来了
dp[i][j] = word1[i-1] === word2[j-1] ?
dp[i-1][j-1] :
(1 + Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]))
最终完成的dp
| dp | “” | r | (ro) o | (ros) s |
| ------------ | -- | ----- | ---------- | ----------- |
| “” | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 | 3 |
| (ho) o | 2 | 2 | 1 | 2 |
| (hor)r | 3 | 2 | 2 | 2 |
| (hors)s | 4 | 3 | 3 | 2 |
| (horse)e | 5 | 4 | 4 | 3 |
代码实现
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
let length1 = word1.length;
let length2 = word2.length;
let dp = new Array(length1 + 1).fill(0).map((item) => {return new Array(length2 + 1).fill(0)});
for (let i = 0; i < dp.length; i++) {
dp[i][0] = i;
}
for (let i = 0; i < dp[0].length; i++) {
dp[0][i] = i;
}
//初始化工作结束
for (let i = 1; i <= length1; i++) {
for (let j = 1; j <= length2; j++) {
dp[i][j] = word1[i-1] === word2[j-1] ? dp[i-1][j-1] : (1 + Math.min(
dp[i-1][j],
dp[i][j-1],
dp[i-1][j-1]
))
}
}
return dp[length1][length2]
};
总结
我们知道vue的diff算法被优化到了O(n)，而此题我们观察发现除了两层循环对比每个元素，还需要min操作，实际时间复杂度到达了O(n3)。
那么vue是如何做到的呢？还记得我们循环节点时需要设置的key。通过这个key，我们就可以一一对应前后节点之间的关系。那我们只需要遍历一次节点就可以了。
