⚔ LeetCode | 72. Edit Distance

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

LeetCode 72. Edit Distance

Difficulty : Hard

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:

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

Example 2:

1
2
3
4
5
6
7
8
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')

Analysis

一般情况下，对于两个字符串，考虑增加、删除、替换来将一个字符串变成另一个字符串，首先就需要将他们对齐，然后对于没有对齐的位置进行操作。如果简单地遍历两个字符串，那么就可能存在非常多的对齐方式，寻找最优的对齐方式无疑计算量是十分大的。

虽然这道题看上去和动态规划并没有什么关系，但是我们可以通过将其划分为子问题然后使用动态规划的思想来解决这道题。

Approach 1

我们先来看看给出来的第一个例子：horse和ros

按照题目的解，可以表示成以下的对齐方式：

h o r s e
r o - s -

可以看到，我们只需要替换第一个字符，删除第三和第五个字符，就可以完成字符串一到字符串二的转换。

那么，如何找到这种最优的对齐方式呢？

首先，我们从最右侧看起：

对于这两个字符串的最右侧看来，只可能存在这三种情况之一：

- x[i] x[i]
y[j] - y[j]

第一种情况，表示需要在第一个字符串中插入y[j]，此时的代价为 1，然后剩下对x[1...i]和y[1...j-1]进行对齐的子问题E(i, j - 1)。这样，我们就成功划分出一个子问题。

同样，对于第二种情况，表示需要删除第一个字符串的x[i]，代价同样为 1，然后剩下对x[1..i-1]和y[1..j]进行对齐的子问题E(i - 1, j )。

最后一种就要分情况讨论：

  • 如果x[i] == y[j]，那么就表示这个字符不需要做任何的操作，代价为 0，然后剩下对x[1..i-1]和y[1..j-1]进行对齐的子问题E(i - 1, j - 1)。
  • 如果x[i] != y[j]，那么就需要对字符进行替换，代价为 1，同样划分出同样的子问题E(i - 1, j - 1)。

其中，这三种情况的最优值，就是其中的代价的最小值。

也就是$E(i, j) = min(E[i - 1, j] + 1, E[i, j - 1] + 1, E[i - 1, j - 1] + (x[i] != y[j ]))$

(注意：这里的x和y的下标是从1开始算，在绝大多数的编程语言中，数组下标都是从 0 开始，因此需要取x[i -1] 和 y[j - 1])

然后一直对两个字符串的子问题进行处理，最后再加起来就是所有的代价。

完成了划分子问题的过程，接下来就需要确定动态规划的基准情形， 也就是最小子问题的值。

在这个问题中，最小子问题就是E(0, *)和E(*, 0)，就代表一个空串和另一个字符串的编辑距离，自然就是另一个字符串的长度，因此可以得到E(0, j) = j、E(i, 0) = i

那么，我们需要按什么顺序求解呢？

因为，最终问题的代价的计算需要依赖之前三个子问题的代价，因此从最小的子问题开始求解，那么后面的问题就可以直接使用前面问题的解而不需要重新计算，这就是动态规划的魅力所在。

因此，我们可以构建一个二维数组，分别对应不同的子问题的代价，然后从上到下，从左到右填充这个二维数组，最终二维数组的右下角的值自然就是我们需要的解。

具体做法如下：

  • 首先定义一个有n+1行和m+1列的二维数组，其中n和m分别为两个字符串的长度。

  • 然后定义最小子问题的代价

    • 填充第一列，其代价等于所在行数

    • 填充第一行，其代价等于所在列数

  • 根据三个子问题的代价计算出下一个问题的代价，就是上面所说到的最小值

​

C++代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int minDistance(string word1, string word2) {
    int len1 = word1.length();
    int len2 = word2.length();
    int mat[len1 + 1][len2 + 1];
    for (int i = 0; i <= len1; i++) {
      mat[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
      mat[0][j] = j;
    }
    for (int i = 1; i <= len1; i++) {
      for (int j = 1; j <= len2; j++) {
        if (word1[i - 1] == word2[j - 1]) {
          mat[i][j] = mat[i - 1][j - 1];
        } else {
           mat[i][j] = min(mat[i - 1][j - 1], min(mat[i - 1][j],  mat[i][j - 1])) + 1;
        }
      }
    }
    return mat[len1][len2];
  }
};

这段代码只需要把表格填充完毕就可以得到解，因此其时间复杂度为O(nm)，其中n和m分别为这两个字符串的长度。在LeetCode上执行只需要4ms,是C++中最优的解法。

Summary

这是一道十分经典的动态规划问题——编辑距离，这道题充分体现了动态规划的特点。在《算法概论》这一书中也有详细的描述，我这里只是将他的描述加以一些自己的理解再描述出来，需要更深入了解动态规划的其他经典问题，如 01 背包问题，最长递增子序列问题还有有向无环图的最短路径问题，都可以去看一看这本书动态规划这一章。

土豪通道
0%