Edition Distance

​ 缘起：前段时间，看dom diff算法那块的时候，看到了列表对比那块用到了edit distance算法，例如p, ul, div 的顺序换成了 div, p, ul。这个该怎么对比？如果按照同层级进行顺序对比的话，它们都会被替换掉。如 p 和div的tagName不同，p会被div所替代。最终，三个节点都会被替换，这样DOM开销就非常大。而实际上是不需要替换节点，而只需要经过节点移动就可以达到，我们只需知道怎么进行移动。

​ 将这个问题抽象出来其实就是字符串的最小编辑距离问题（Edition Distance），最常见的解决方法是 Levenshtein Distance , Levenshtein Distance 是一个度量两个字符序列之间差异的字符串度量标准，两个单词之间的 Levenshtein Distance 是将一个单词转换为另一个单词所需的单字符编辑（插入、删除或替换）的最小数量。Levenshtein Distance 是1965年由苏联数学家 Vladimir Levenshtein 发明的。Levenshtein Distance 也被称为编辑距离（Edit Distance），通过动态规划求解，时间复杂度为 O(M*N)。

72. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

if s1[i] == s2[j]:
	啥都别做（skip）
    编辑距离
    i, j 同时向前移动
else:
	三选⼀：
    	插⼊（insert）
        删除（delete）
        替换（replace）

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let m=word1.length,
        n=word2.length;
    const dp=Array(m+1).fill(0).map(x=>Array(n+1).fill(0));
    for(let i=1;i<m+1;i++) {
        dp[i][0]=i;
    }
    for(let i=1;i<n+1;i++) {
        dp[0][i]=i;
    }
    for(let i=1;i<=m;i++) {
        for(let j=1;j<=n;j++) {
            //本来就相等，不需要任何操作
            //s1[0..i] 和 s2[0..j] 的最⼩编辑距离等于
            //s1[0..i-1] 和 s2[0..j-1] 的最⼩编辑距离
            //也就是说 dp(i, j) 等于 dp(i-1, j-1)
            if(word1[i-1]===word2[j-1]) dp[i][j]=dp[i-1][j-1];
            else {
                dp[i][j]=Math.min(
                    //我直接把 s[i] 这个字符删掉
                    //前移 i，继续跟 j 对⽐
                    dp[i-1][j]+1, //删除
                    //我直接在 s1[i] 插⼊⼀个和 s2[j] ⼀样的字符
                    //那么 s2[j] 就被匹配了，前移 j，继续跟 i 对⽐
                    dp[i][j-1]+1, //插入
                    //我直接把 s1[i] 替换成 s2[j]，这样它俩就匹配了
                    //同时前移 i，j 继续对⽐
                    dp[i-1][j-1]+1 //替换
                )
            }
        }
    }
    return dp[m][n];
};