编辑距离

给你两个单词 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 <= 500
• word1 和 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进行对比操作。先使用动态规划解决。

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

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]时。实际代码就出来了

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

代码实现

/**
 * @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(n^3)。

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