此题是一个最短编辑距离问题，我们在工作中用到工具和框架有很多也是类似的算法。比如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进行对比操作。先使用动态规划解决。

1. 首先构建一个二维数组用来记录子问题的解。

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]的值。

1. dp[1][1]处，word1为h，word2为r。两位不同,那么有三种处理方式
   1. h -> r 更改h,操作数为1，修改之后变成了 r和r，参照说明中的第二条，我们再加上dp[0][0]即可
   2. word2增加h变为rh,操作数为1, h和rh参照说明中的第二条，就变成了‘’ => "r"所用的步数，dp[0][1]
   3. word1增加r变为hr,操作数为1, hr和r参照说明中的第二条，就变成了‘h’ => ""所用的步数，dp[1][0]
2. 当我们分析出了以上三种情况后，我们肯定要取最小值作为我们此次dp[1][1]所要求出来的值了。
3. 转换为代码就是 1 + Math.min(dp[0][0],dp[0][1],dp[1][0])
4. 以上是末尾不相同的情况，如果相同，请参照说明第二条。实际上就是和横纵各退一步的情况相同
5. 最后我们将dp[i][j]看作此次dp[1][1]时。实际代码就出来了

复制
1dp[i][j] = word1[i-1] === word2[j-1] ? 
2	dp[i-1][j-1] : 
3	(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

代码实现

复制
1/**
2 * @param {string} word1
3 * @param {string} word2
4 * @return {number}
5 */
6var minDistance = function(word1, word2) {
7    let length1 = word1.length;
8    let length2 = word2.length;
9
10    let dp = new Array(length1 + 1).fill(0).map((item) => {return new Array(length2 + 1).fill(0)});
11
12    for (let i = 0; i < dp.length; i++) {
13        dp[i][0] = i;
14    }
15    for (let i = 0; i < dp[0].length; i++) {
16        dp[0][i] = i;
17    }
18    //初始化工作结束
19    for (let i = 1; i <= length1; i++) {
20        for (let j = 1; j <= length2; j++) {
21            dp[i][j] = word1[i-1] === word2[j-1] ? dp[i-1][j-1] : (1 + Math.min(
22                dp[i-1][j], 
23                dp[i][j-1],
24                dp[i-1][j-1]
25            ))
26        }
27    }
28    return dp[length1][length2]
29
30};

总结

我们知道vue的diff算法被优化到了O(n)，而此题我们观察发现除了两层循环对比每个元素，还需要min操作，实际时间复杂度到达了O(n^3)。

那么vue是如何做到的呢？还记得我们循环节点时需要设置的key。通过这个key，我们就可以一一对应前后节点之间的关系。那我们只需要遍历一次节点就可以了。