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

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

原题目按此：72. 编辑距离 - 力扣（LeetCode）。

题目描述

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

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

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

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

开始

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

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

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

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

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

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

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

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

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

      horse
i:        ↑
   
        ros
j:        ↑

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

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

horses
    ↑

   ros
    ↑

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

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

hors
   ↑

 ros
   ↑

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

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

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

因此，我们得到递归公式²：

\[ 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. 计算最优解的值

带备忘的自顶向下

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

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]），所依赖三个子问题都在它的左边、上面和左上角。只要按照一定顺序计算，就能生成整张表。

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]，以此类推。

代码：

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);
    }
}

输出的结果：

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')

完整代码：这里。

希望能对你有所帮助。

---

参见：

• 《算法导论》
• 详解一道经典面试题：编辑距离 - 知乎
• 自底向上 和自顶向下 - 编辑距离 - 力扣（LeetCode）

---

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

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