继上一篇 #104 ，本来是在研究虚拟 DOM 算法的，看到了 livoras 的这篇文章，觉得写得很好！珠玉在前，我便不再赘述了。该文章中提到：列表更新本质上是一个最小编辑距离问题，不过并未就此详细展开。今天，我们来具体看看这个问题。

问题

给定两个字符串 a 和 b，只允许以下三种操作：

1. 插入一个字符；
2. 删除一个字符；
3. 替换一个字符。

求：把 a 转换成 b 的最小操作次数，也就是所谓的最小编辑距离。
举例： "xy" => "xz"，只需要把 y 替换成 z，因此，最小编辑距离为 1。
"xyz" => "xy"，只需要删除 z ，因此，最小编辑距离为 1。

求解这个问题，一般有两种思路：递归和动态规划。

递归

所谓递归，便是把大问题”分治“成类似的小问题。
假设，a 的长度是 m，b 的长度是 n，要求 a[1]a[2]...a[m] => b[1]b[2]...b[n] 的最小编辑距离，记为 d[m][n]。

1. 如果 a[m] === b[n]，那么问题转化为求解：a[1]a[2]...a[m-1] => b[1]b[2]...b[n-1] 的最小编辑距离，因此 d[m][n] === d[m-1][n-1]。比如，"xyz" => "pqz" 的最小编辑距离等于 "xy" => "pq" 的最小编辑距离。
2. 如果 a[m] !== b[n]，又分为三种情况：
   1. 比如，"xyz" => "efg" 的最小编辑距离等于 "xy" => "efg" 的最小编辑距离 1（因为允许插入操作，插入一个 "z"），抽象的描述便是 d[m][n] === d[m-1][n] 1。
   2. 比如，"xyz" => "efg" 的最小编辑距离等于 "xyzg" => "efg" 的最小编辑距离 1，且因为最后一个字符都是 "g"，根据第一个判断条件，可以再等于 "xyz" => "ef" 的最小编辑距离 1，因此，得到结论："xyz" => "efg" 的最小编辑距离等于 "xyz" => "ef" 的最小编辑距离 1，抽象的描述便是：d[m][n] === d[m][n-1] 1。
   3. 比如，"xyz" => "efg" 的最小编辑距离等于 "xyg" => "efg" 的最小编辑距离 1（因为允许替换操作，可以把 "g" 换成 "z"），再等于 "xy" => "ef" 的编辑距离 1（根据第一个判断条件），抽象的描述便是： d[m][n] === d[m-1][n-1] 1。
   4. 上述三种情况都有可能出现，因此，取其中的最小值便是整体上的最小编辑距离。
3. 如果 a 的长度为 0，那么 a => b 的最小编辑距离为 b 的长度；反过来，如果 b 的长度为 0，那么 a => b 的最小编辑距离为 a 的长度。

代码实现

/**
 * 递归算法
 * @param {string} a
 * @param {string} b
 * @param {number} i 字符串 a 的长度
 * @param {number} j 字符串 b 的长度
 * @returns {number} 从 a → b 的最小编辑距离
 */
function recursion(a, b, i, j) {
    if (j === 0) {
        return i;
    } else if (i === 0) {
        return j;
    } else if (a[i - 1] === b [j - 1]) {
        return recursion(a, b, i - 1, j - 1);
    } else {
        let m1 = recursion(a, b, i - 1, j)   1;
        let m2 = recursion(a, b, i, j - 1)   1;
        let m3 = recursion(a, b, i - 1, j - 1)   1;
        return Math.min(m1, m2, m3);
    }
}

动态规划

动态规划看起来跟递归很像，不过推理逻辑正好是反过来的。递归的逻辑是：“要求得 d[m][n]，先要求得 d[m-1][n-1]……”，动态规划的逻辑是：“先求得 d[m-1][n-1]，再求 d[m][n]……”这是它们的主要区别。
举个例子，在已知 d[0][0]，d[0][1]，d[1][0] 的前提下，要求 d[1][1]：

1. 如果 a[1] === b[1]，那么 d[1][1] 等于 d[0][0]，也就是 0；
2. 如果 a[1] !== b[1]，那么 d[1][1] 等于 d[0][1]、d[1][0] 和 d[0][0] 三者中的最小值 1，也就是 1。

接着用同样的方式，可以求得 d[1][2]、d[1][3]、……、d[1][n]，然后继续求得 d[2][1]、d[2][2]、……、d[2][n]，一直到 d[m][n]。代码实现如下：

/**
 * 动态规划算法
 * @param {string} a
 * @param {string} b
 * @returns {number} 从 a → b 的最小编辑距离
 */
function dynamicPlanning(a, b) {
    let lenA = a.length;
    let lenB = b.length;
    let d = [];
    d[0] = [];

    for (let j = 0; j <= lenB; j  ) {
        d[0].push(j);
    }

    for (let i = 0; i <= lenA; i  ) {
        if (d[i]) {
            d[i][0] = i;
        } else {
            d[i] = [];
            d[i][0] = i;
        }
    }

    for (let i = 1; i <= lenA; i  ) {
        for (let j = 1; j <= lenB; j  ) {
            if (a[i - 1] === b[j - 1]) {
                d[i][j] = d[i - 1][j - 1];
            } else {
                let m1 = d[i - 1][j]   1;
                let m2 = d[i][j - 1]   1;
                let m3 = d[i - 1][j - 1]   1;
                d[i][j] = Math.min(m1, m2, m3);
            }
        }
    }

    return d[lenA][lenB];
}

对比与实证

这两种算法哪一个更快呢？
我不知道如何从理论上去计算其时间复杂度和空间复杂度，因为对于复杂度的计算，我只能应付那种简单的，比如 n 重循环，我知道其时间复杂度是 n 次方。但是，对于这种稍微复杂一些的程序，我便不知所措了。
怎么办呢？ → 我决定从实证的角度去得到答案，也就是说，通过实际测量程序的运行时间，来衡量其时间复杂度。
我使用 jsPerf，建了一个 Test Case，从链接进去点击“Run Tests”，稍等片刻，便能看到程序运行的速度（指标 ops/sec 为 1s 内程序重复执行次数，数值越高代表程序运行越快），具体执行结果如下图所示。

从图中我们可以看到：递归的时间复杂度是指数级的，动态规划的时间复杂度是线性级的。
为什么动态规划快那么多呢？ → 从代码上我们能猜测一二：**动态规划需要存储一个矩阵d[m][n]，随着规模的增大，矩阵变得越来越大，对内存的占用也是越来越多的。这本质上是在用空间换时间。**当然，也是有办法可以优化其占用空间的，具体的可以看参考资料中明无梦的文章。另外，目前我还不知道该如何实际测量程序的空间复杂度，如果有知道的朋友，还望不吝赐教。

参考资料

1. 编辑距离, By 明无梦
2. 动态规划求编辑距离, By 残阳似血