Leetcode 72:编辑距离 - 动态规划的解题思路

记录题解,也借这个过程捋一捋动态规划的思路和方法。

原题目按此:72. 编辑距离 - 力扣(LeetCode)

题目描述

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

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

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

比如 horse 转换到 ros 所需要的最小操作数是 3,或者说 horseros 的距离是 3.

开始

能够用动态规划求解的问题通常具有下面的几个特点:

  1. 让你求某个问题的一个最优解
  2. 这个问题能够拆分成更小的子问题(递归求解/分治法)
  3. 会重复求解相同的子问题

满足这些条件,这个问题就是一个动态规划问题了。求解问题也是按照这些步骤来进行。

我们根据《算法导论》上面提供的步骤来。

1. 刻画一个最优解的结构特征

“如果一个问题的最优解包含其子问题的最优解,我们就称此问题具有最优子结构性质。”1

也就是说这一步我们需要正确的划分子问题,让子问题有最优解的时候,原问题也有最优解。想办法找到和原问题形式一样,但是规模比较小的问题。

所以我们可以考虑,两个字符串的距离,可以由另外两个字符串的距离的基础上,插入/删除/替换了一个字符来得到。

设置两个指针 i 和 j,分别放在原字符 word1 和替换字符 word2 的最后,指针从右往左移,操作 word1[i],让它和 word2[j] 相同。指针经过的地方代表这一部分的字符串已经完成了转换。

1
2
3
4
5
      horse
i: ↑

ros
j: ↑

那么,对每一个字符,这边就以 horse 的 e 作为例子,我们能有这么几种操作:

1 在 e 的右边插入字符 s。

1
2
3
4
5
horses


ros

假如我们知道 horse -> ro 的距离为 n,那么总编辑距离就是 n+1。

2 删除字符 e。接下来需要计算 hors -> ros 的距离。距离 +1。

1
2
3
4
5
hors


ros

3 把 e 替换成 s。接下来需要计算 hors -> ro 的距离。注意,这里如果两个字母相同,就不用转换了,这时候相当于代价为0,直接等价于子问题。

1
2
3
4
5
horss


ros

对于这一个字符的修改,相当于是做出了一种选择:我们不知道对这个字符 e 怎么处理最终编辑的距离会最短,所以假设每一种可能性都是最优解并且去尝试。通过上面的例子我们发现,子问题中需要求的字符串长度已经缩短了,说明这种方法是可行的。

2. 递归地定义最优解的值

设 m[i, j] 表示 word1[0..i] 到 word2[0..j] 的距离,几个子问题就可以表示成这样:

  • 当 word1[i] == word2[j] 时,m[i, j] = m[i-1, j-1];

  • 当 word1[i] != word2[j] 时,m[i, j] 可以是:

    • m[i, j-1] + 1
    • m[i-1, j] + 1
    • m[i-1, j-1] +1

    在它们中选距离最短的一个。

因此,我们得到递归公式2

\[ m[i, j]=\left\{ \begin{array}{lr} m[i-1, j-1] & w1[i] = w2[j]\\ min(m[i, j-1] + 1,\ m[i-1, j] + 1,\ m[i-1, j-1] +1) & w1[i] \neq w2[j] \end{array} \right. \]

因为是递归求解,需要考虑一下递归的终止条件:当 i 或 j 等于 -1 时,是空值和字符串之间的转换,显然从空到长度为 n 的字符串的距离就是 n。即:

  • m[-1, j] = j + 1
  • m[i, -1] = i + 1

再完善一下公式:

\[ m[i, j]=\left\{ \begin{array}{lr} j + 1 & i=-1\\ i + 1 & j=-1\\ m[i-1, j-1] & w1[i] = w2[j]\\ min(m[i, j-1] + 1,\ m[i-1, j] + 1,\ m[i-1, j-1] +1) & w1[i] \neq w2[j] \end{array} \right. \]

写出递归式之后,我们已经把一个应用问题转化成了数学问题。接下来就是编程时间,把它转化成代码了😉。

3. 计算最优解的值

带备忘的自顶向下

自顶向下法比较贴近我们的思考方式。它比递归更进一步,会保存每一步的计算结果。这样在需要一个子问题的解之前会先检查是不是已经计算过了,如果是的话就直接使用保存过的值。

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
class Solution {
int[][] dist;

public int minDistance(String word1, String word2) {
int l1 = word1.length();
int l2 = word2.length();
dist = new int[l1][l2];

for (int i=0; i<l1; i++) {
for (int j=0; j<l2; j++) {
dist[i][j] = -1; //用 -1 来代表没有计算过的部分
}
}

return calcDistance(word1, word2, l1-1, l2-1);
}

private int calcDistance(String w1, String w2, int i, int j) {
if (i==-1) return j+1;
if (j==-1) return i+1;
if (dist[i][j]!=-1) return dist[i][j];

int res;
if (w1.charAt(i)==w2.charAt(j)) {
res = calcDistance(w1, w2, i-1, j-1);
}
else {
int add = calcDistance(w1, w2, i, j-1)+1;
int rem = calcDistance(w1, w2, i-1, j)+1;
int repl = calcDistance(w1, w2, i-1, j-1)+1;

res = Math.min(Math.min(add, rem), repl);
}

dist[i][j] = res;
return res;
}
}

这里用二维数组 dist[][] 来保存计算过的距离,用值 -1 表示未计算过的距离。

自底向上

自底向上的方法采用的是这么一种思路:先求解规模小的问题,再求解规模大的问题。在求解一个问题的时候,它所依赖的子问题都以经被计算过了。这样的好处在于可以不用使用递归函数调用,也不需要检查子问题是否计算过。

编辑距离表格

这张表是 horse -> ros 每个长度编辑距离的表格,和上面自顶向下代码中的 dist 数组存储的数据差不多,多了一行一列的边界值,也就是终止条件的情况。应该能够很直观地看到,表格中的每一个值(m[i, j]),所依赖三个子问题都在它的左边、上面和左上角。只要按照一定顺序计算,就能生成整张表。

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
class Solution {
public int minDistance(String word1, String word2) {
int l1 = word1.length();
int l2 = word2.length();

int[][] dist = new int[l1+1][l2+1];

for (int i=0; i<=l1; i++)
dist[i][0] = i;

for (int j=0; j<=l2; j++) {
dist[0][j] = j;
}

for (int i=1; i<=l1; i++) {
for (int j=1; j<=l2; j++) {
if (word1.charAt(i-1)==word2.charAt(j-1)) {
dist[i][j] = dist[i-1][j-1];
}
else {
int add = dist[i][j-1]+1;
int rem = dist[i-1][j]+1;
int repl = dist[i-1][j-1]+1;
dist[i][j] = Math.min(repl, Math.min(rem, add));
}
}
}

return dist[l1][l2];
}
}

4. 利用计算出的信息构造一个最优解

让我们更进一步!

到上面为止,对于解答问题——得到单词间的最小距离,已经完成了。但是假如我们想要知道具体的每一步应该怎么编辑字符,该怎么做呢?我们可以对代码稍加修改,使每一个问题不仅保存最优解的值,还把相应的操作保存下来。

另外定义一个二维数组 act[][] 来储存操作,用值 0~3 来表示跳过、插入、删除和替换的操作,在找到最短距离的同时顺便记录下对应的操作,就能得到一张操作表。

编辑操作表格

假如 act[i][j] 当前的值是 2,代表删除,那么就删除 word1[i] 的字符,然后往上移,寻找 act[i-1][j],以此类推。

代码:

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
public void printOperations(int[][] act,int i,int j, String w1, String w2) {
System.out.println(w1 + " -> " + w2 + ":");
while (i!=0 && j!=0) {
String tmp;
String s = "";
switch (act[i][j]) {
case 0:
//s = "(跳过)\n";
i--;
j--;
break;
case 1:
tmp = w1.substring(0, i) + w2.charAt(j-1) + w1.substring(i+1);
s = String.format("%s -> %s (插入 '%c')\n", w1, tmp, w2.charAt(j-1));
w1 = tmp;
j--;
break;
case 2:
tmp = w1.substring(0, i-1) + w1.substring(i);
s = String.format("%s -> %s (删除 '%c')\n", w1, tmp, w1.charAt(i-1));
w1 = tmp;
i--;
break;
case 3:
tmp = w1.substring(0, i-1) + w2.charAt(j-1) + w1.substring(i);
s = String.format("%s -> %s (将 '%c' 替换为 '%c')\n",
w1, tmp, w1.charAt(i-1), w2.charAt(j-1));
w1 = tmp;
i--;
j--;
break;
}
System.out.print(s);
}
}

输出的结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
horse -> ros:
horse -> hors (删除 'e')
hors -> hos (删除 'r')
hos -> ros (将 'h' 替换为 'r')

intention -> execution:
intention -> intenuion (插入 'u')
intenuion -> intecuion (将 'n' 替换为 'c')
intecuion -> inecuion (删除 't')
inecuion -> ixecuion (将 'n' 替换为 'x')
ixecuion -> execuion (将 'i' 替换为 'e')

consistent -> constraint:
consistent -> consistint (将 'e' 替换为 'i')
consistint -> consisaint (将 't' 替换为 'a')
consisaint -> consiraint (将 's' 替换为 'r')
consiraint -> constraint (将 'i' 替换为 't')

希望能对你有所帮助。


参见:


  1. 《算法导论(原书第3版)》,(美)科尔曼(Cormen, T. H.)等著;殷建平等译,机械工业出版社,2013.1,15.3章 动态规划原理,P216。↩︎

  2. 递归公式,也叫状态转移方程。注意不是“递推”,递归是自顶向下的,而递推是自底向上的。↩︎