详解编辑距离(Levenshtein 距离)算法

目标

72. 编辑距离

给你两个单词 word1word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符

  • 删除一个字符

  • 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

说实话,我看不懂 LC 上的题解——虽然看完能照猫画虎代码,但是对于原理还是不清不楚。不给实例分析的题解都是耍流氓(暴论)。

概念铺垫

代表串:假设有字符串 w,则下标 i 处的字符为 w[i],其代表串为 w[i]之前的子串(切片) w[0:i-1](也即 w 从头算起长度为 i 的子串)。

举个例子,现有字符串 pluveto,则 w[3] 代表串为 pluw[0] 代表串为 $\varepsilon$ (空串)。

【定义】 $f(i,j)$ 表示将 w[i] 代表串,变成 w[j] 代表串所需的最小步骤数。

这里的步骤,就是执行操作的个数,允许的操作已经在题目中给出。

DP 表的解释

以下面的表为例,从上到下是 i 增加的方向,从左到右是 j 增加的方向。坐标从 0 起(对应轴上的空白),比如下面写着 0 的格子,其坐标是 $(0,0)$.

image-20211116130103287

初始化 DP 数组,尝试寻找规律

$f(0,0)$ ,将 (空串) 变成 (空串) 需要 0 步,无脑填 0.

image-20211116130103287

$f(0,1)$,将空串变 a 需要一步插入,填 1.

image-20211116130248455

f(0,2),将空串变 ab 需要两步插入,填 2. 相当于 $f(0,1) + 1$。

image-20211116130311488

同理:

image-20211116130339793

接下来,将 f(1) 所代表的串 a 变成空串,需要 1 步删除。

image-20211116130454338

同理,将 (2,0) 代表的串 ab 变成空串,需要 2 步删除。相当于 $f(1,0)+1$。

image-20211116130544923

其余同理。

image-20211116130624884

归纳:如何利用历史状态计算新状态?

重点来了。下面我们填写 $f(1,1)$。即w1[1] 的代表串 a 变成 w2[1] 的代表串 a(本次求值目标)

image-20211116142625573

(请时刻关注上面这个求职目标的位置)

我们有三种操作的方法,插入,删除,替换,对应三种情况:

插入的情况

第一种情况,先将 w1[i-1] 代表串变成即 w2[i] 代表串。需要 f(0,1)=1 次操作:

image-20211116131028633

这种操作之后,再将 w1[i-1] 代表串之后插入一个 a,即可得到本次求值目标。这种情况下 $f(1,1) = f(0,1) + 1 = 1+1=2$。

其中 f(1,1) 表示本次求值目标,

f(0,1) 表示 w1[i-1] 代表串变成 w2[i] 代表串 所需次数,查表得到 $1$。

1 表示 w1[i-1] 代表串 之后再插入一个 a 这一次动作的计数。

替换的情况

第二种情况,先将 w1[i-1] 代表串(空串)变成 w2[i-1] 代表串(空串)。需要 f(0,0)=0 次操作。

image-20211116131612384

然后再把 w2[i] 代表串替换为 w1[i] 即可得到本次求值目标,实现两串相同。由于替换的字符恰好等于 w2[i] 的字符,即不需要替换,即代价为 0。这种情况下,$f(1,1)=f(0,0)+0=0$.

删除的情况(等价于插入)

第三种情况,先将 w1[i] 代表串 a 经过变成 w2[j-1] 代表串(空串)。查表需要 f(1,0)=1 次操作。

image-20211116131612384

然后再在w2[j-1] 代表串(空串)之后插入一个 a 即可得到本次求值目标,这种情况下,进行了一次操作,代价为 1,$f(1,1)=f(1,0)+0=1+0=1$.

也可以理解为在 w1[i] 最后删除一个 a,对 w2 插入和对 w1 删除就代价和效果而言是等价的

image-20211116132110812

上面三种操作,代价最小的是第二种,所以我们取 $f(1,1)=\min(1,0,1) = 0$:

image-20211116132252326

发现,实际上求 $f(i,j)$,就是求左上角、正上方、正左方的(单元格的值各自与其对应后续操作的开销的和)的最小值: $\min\{f(i-1,j) + c_1,f(i-1,j-1)+c_2,f(i,j-1)+c_3\} = \min(C_1,C_2,C_3)$

有个细节在于 $c_1,c_2,c_3$ 的计算。$c_1,c_3$ 是插入和删除操作(或者可以都看成插入),开销固定是 1.

$c_2$ 是替换操作,w1[i] == w2[i] 即字符相同时不用替换,开销是 0,不同时替换,开销是 1.

至于为啥?

为了读者更好地理解,我们不糊弄过去,下面看个例子。求值目标是 $f(i,j) = f(3,2)$:

image-20211116140338877

在这一步发现。周围开销最小的是上方,即 $f(i-1,j)=f(2,2)=0$,即意味着,只要经过 0 步,就可以把 w1[i-1] 代表串 ab,变成 $w2[j]$ 代表串 ab. 这没问题。此时 w1[i]==w2[j]=='b',我们怎么办?

我们令 $C_1 = f(i-1,j) + c_1$ $C_2 = f(i-1,j-1) + c_2$ $C_3 = f(i,j-1) + c_3$

  • 怎么求 $C_1$ ?让 w1[i-1] 代表串 ab 变成 w2[j] 代表串 ab 的开销是 0,要经过一步插入,所以 $c_1 =1$,$C_1 = 1+1=2$

  • 同理让 w1[i] 代表串 abb 变成 w2[j-1] 代表串 a 的开销是 2(上表 $f(i,j-1)$),然后要经过一步删除,所以 $c_3 =1 $,$C_3 = 2+1=3$

  • 再看 $C_2$,由于 $f(i-1,j-1)$ 即让 w1[i-1] 代表串(ab)变成 w2[j-1] 代表串(a)的开销是 $f(i-1,j-1) = 1$,而 w1[i]==w2[j],所以 $c_2 = 0$,故 $C_2 = 1+0 = 1$

所以 $f(i,j) = \min \{C_1,C_2,C_3\} = \min\{2,1,3\} = 1$:

image-20211116141024276

重复此过程,得到:

image-20211116141126811

最右下角就是答案:

image-20211116141223357

用代码表达出来

掌握了手算的方法,剩下的就是代码实现。

参考代码:

 1inline int min3(int a, int b, int c) {
 2  return a < b ? (c < a ? c : a) : (b > c ? c : b);
 3}
 4
 5class Solution {
 6public:
 7  int minDistance(string w1, string w2) {
 8    int n = w1.size();
 9    int m = w2.size();
10    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
11    // -- 初始化基本情况
12    // +-------> y
13    // |
14    // x
15    //
16    // 第一列的各行
17    for (int i = 1; i <= n; i++) {
18      dp[i][0] = i;
19    }
20    // 第一行的各列
21    for (int j = 1; j <= m; j++) {
22      dp[0][j] = j;
23    }
24    // -- 开始 DP
25    for (int i = 1; i <= n; i++) {   // 各行
26      for (int j = 1; j <= m; j++) { // 各列
27        auto c1 = dp[i - 1][j] + 1;  // 上
28        auto cc2 = w1[i - 1] == w2[j - 1] ? 0 : 1;
29        auto c2 = dp[i - 1][j - 1] + cc2; // 左上
30        auto c3 = dp[i][j - 1] + 1;   // 左
31        dp[i][j] = min3(c1, c2, c3);
32      }
33    }
34
35    return dp[n][m];
36  }
37};

空间优化

$f(i,j)$ 只依赖当前行和前一行。但是初始化的时候却要初始化最左列全部。如果优化为 $O(m)$ 空间,势必要破坏最左列的初始化。但是注意到初始化的结构和遍历的结构很像,只要把“第一列的各行”初始化放到后面就行:

 1class Solution {
 2public:
 3  int minDistance(string w1, string w2) {
 4    int n = w1.size();
 5    int m = w2.size();
 6    int d = 2;
 7    vector<vector<int>> dp(d, vector<int>(m + 1, 0));
 8    // 第一行的各列
 9    for (int j = 1; j <= m; j++) {
10      dp[0][j] = j;
11    }
12    // -- 开始 DP
13    for (int i = 1; i <= n; i++) { // 各行
14      dp[i % d][0] = i; // 初始化移动到这儿了
15      for (int j = 1; j <= m; j++) {      // 各列
16        auto c1 = dp[(i - 1) % d][j] + 1; // 上
17        auto cc2 = w1[i - 1] == w2[j - 1] ? 0 : 1;
18        auto c2 = dp[(i - 1) % 2][j - 1] + cc2; // 左上
19        auto c3 = dp[i % d][j - 1] + 1;
20        dp[i % d][j] = min3(c1, c2, c3);
21        // print_vec_2d(dp);
22      }
23    }
24
25    // print_vec_2d(dp);
26
27    return dp[n % 2][m];
28  }
29};

优化后的空间复杂度变成 $O(2m)$,有所进步。

image-20211116151354731

进一步空间优化

我们还可以进一步优化为 $O(m)$,即只用一个额外数组。画个图就懂了:

image-20211116153132242

可以注意到,每一步所依赖的范围,只有这一行的元素个数+1,即 $m+1$。其余左上角前面的值、问号后面的值是什么,我们并不关心。据此,可以滚动这个 m+1 的空间求值。

image-20211116153053355

下面是进一步优化的结果:

 1class Solution {
 2public:
 3  int minDistance(string w1, string w2) {
 4    int n = w1.size();
 5    int m = w2.size();
 6    if (n == 0)
 7      return m;
 8    if (m == 0)
 9      return n;
10    std::vector<int> dp(m + 1);
11    for (int c = 0; c < m + 1; c++) {
12      dp[c] = c;
13    }
14    for (int r = 1; r < n + 1; r++) {
15      int pre = r;
16      for (int c = 1; c < m + 1; c++) {
17        int cur = min(dp[c], pre) + 1;
18        if (w1[r - 1] == w2[c - 1]) {
19          cur = min(cur, dp[c - 1]);
20        } else {
21          cur = min(cur, dp[c - 1] + 1);
22        }
23        dp[c - 1] = pre;
24        pre = cur;
25        if (c == m)
26          dp[c] = cur;
27      }
28    }
29    return dp[m];
30  }
31};