动态规划求解最短编辑距离

在研究 React list diff 算法的过程中，发现了一个有趣的问题，即给定任意两个字符串 s1 与 s2，求将 s1 通过以下操作转换成 s2 的最少步骤 （每执行一次操作，s1 到 s2 的编辑距离加 1）。

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

具体举例，现有 s1='abc' 和 s2='cbef'，求 s1 到 s2 的最短编辑距离 dis（记 dis[m][n] 为 s1<[1]..[m]> 到 s2<[1]…[n]>的最短编辑距离）。下表展示了 s1 到 s2 不同长度子字符串的最短编辑距离：

s1\s2 0(‘’) 1(‘c’) 2(‘cb’) 3(‘cbe’) 4(‘cbef’)
0(‘’) dis[0][0]=0 dis[0][1]=1 dis[0][2]=2 dis[0][3]=3 dis[0][4]=4
1(‘a’) dis[1][0]=1 dis[1][1]=1 dis[1][2]=2 dis[1][3]=3 dis[1][4]=4
2(‘ab’) dis[2][0]=2 dis[2][1]=2 dis[2][2]=1 dis[2][3]=2 dis[2][4]=3
3(‘abc’) dis[3][0]=3 dis[3][1]=2 dis[3][2]=2 dis[3][3]=2 dis[3][4]=3

从上表可以看出两个规律：

  • 若其中一个字符串为空，则最短编辑距离即为另一个字符串的长度，即 dis[m][0]=m 或 d[0][n]=n

  • 若已知 dis[m-1][n]，dis[m][n-1] 与 dis[m-1][n-1]

    • s1[m] === s2[n]，则 dis[m][n] = dis[m-1][n-1]
    • s1[m] !== s2[n]，则 dis[m][n] = min(dis[m-1][n], dis[m][n-1], dis[m-1][n-1]) + 1。

    比如 ‘abc’ -> ‘cac’，由于最后一个字符 ‘c’ 相同，则 ‘abc’ -> ‘cac’ 等价于 ‘ab’ -> ‘ca’，对于 ‘ab’ -> ‘ca’，最后一个字符并不相同，那么 ‘ab’ -> ‘ca’ 可以通过三种途径达到：

    • 先从 ‘ab’ 中删除 ‘b’，然后让 ‘a’ -> ‘ca’
    • 先从 ‘ca’ 中删除 ‘a’，然后让 ‘ab’ -> ‘c’
    • 先让 ‘a’ -> ‘c’，然后将 ‘ab’ 中的 ‘b’ 替换成 ‘ca’ 中的 ‘a’

    综上可知，无论是 ‘a’ -> ‘ca’，’ab’ -> ‘c’ 还是 ‘a’ -> ‘c’ 都需要经过额外的一步编辑，因此只要在求得三种方式最短编辑距离的最小值之后再加 1 即可。

贴上源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
  /**
 * 动态规划算法
 * @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];
}