2. 编辑距离

本节参考 经典动态规划：编辑距离 (opens new window)

题目（来自 LeetCode 第 72 题）

给你两个单词 s1 和 s2， 请返回将 s1 转换成 s2 所使用的最少操作数 。

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

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

示例：

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

提示：s1 和 s2 由小写英文字母组成

2.1 思路

需要明确的是，不管是把s1变成s2还是反过来，结果都是一样的，所以后文就以s1变成s2举例。

之前在“最长公共子序列”题目中说过，解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。

设 s1= “red”，s2 = “apple”，为了把 s1 变成 s2，算法会这样进行：

• 可知至少 5 步。

从上面这个过程可以看出，指针移动过程一共有四种操作：题目允许的三种（插删换）和 skip（什么都不做）。比如当指针所指的两个字符相等时便采取 skip 操作，因为这两个字符本来就相同，为了使编辑距离最小，显然不应该对它们有任何操作，直接往前移动 i,j 即可。

还有一个很容易处理的情况，就是 j 走完 s2 时，如果 i 还没走完 s1，那么只能用删除操作把 s1 缩短为 s2。类似的，如果 i 走完 s1 时 j 还没走完了 s2，那就只能用插入操作把 s2 剩下的字符全部插入 s1。等会会看到，这两种情况就是算法的 base case。

2.2 代码详解

先梳理一下之前的思路：

• base case 是 i 走完 s1 或 j 走完 s2，可以直接返回另一个字符串剩下的长度
• 对于每对儿字符 s1[i] 和 s2[j]，可以有四种操作：

if s1[i] == s2[j]:
    啥都别做（skip）
    i, j 同时向前移动
else:
    三选一：
        插入（insert）
        删除（delete）
        替换（replace）

有这个框架，问题就已经解决了。读者也许会问，这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁。这里用到递归的技巧：

def minDistance(s1, s2) -> int:
    # 定义：dp(i, j) 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
    def dp(i, j):
        # base case
        if i == -1: return j + 1
        if j == -1: return i + 1
        
        if s1[i] == s2[j]:
            return dp(i - 1, j - 1)  # 啥都不做
        else:
            return min(
                dp(i, j - 1) + 1,    # 插入
                dp(i - 1, j) + 1,    # 删除
                dp(i - 1, j - 1) + 1 # 替换
            )
    
    # i，j 初始化指向最后一个索引
    return dp(len(s1) - 1, len(s2) - 1)

理解这里的关键是明确 dp 函数的定义： dp(i, j) 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离。

还有点小问题就是，这个解法是暴力解法，存在重叠子问题，需要用动态规划技巧来优化。

2.3 动态规划优化

对于重叠子问题，优化方法无非是备忘录或者 DP table。

2.3.1 备忘录的方法

备忘录很好加，原来的代码稍加修改即可：

def minDistance(s1, s2) -> int:
    # 备忘录
    memo = dict()
    def dp(i, j):
        if (i, j) in memo: 
            return memo[(i, j)]
        ...
        
        if s1[i] == s2[j]:
            memo[(i, j)] = ...  
        else:
            memo[(i, j)] = ...
        return memo[(i, j)]
    
    return dp(len(s1) - 1, len(s2) - 1)

• 用 memo 作为 dp 函数计算结果的缓存

2.3.2 DP table 的解法

由于二维数组的最小索引是 0，而用来指示字符串 s1 和 s2 的指针索引的 base case 是 -1，因此 dp 数组会偏移一位。所以 dp 数组的定义是：dp[i+1][j-1] 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离。

既然 dp 数组和递归 dp 函数含义一样，也就可以直接套用之前的思路写代码，唯一不同的是，DP table 是自底向上求解，递归解法是自顶向下求解：

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i-1][j-1]
    int[][] dp = new int[m + 1][n + 1];
    // base case 
    for (int i = 1; i <= m; i++)
        dp[i][0] = i;
    for (int j = 1; j <= n; j++)
        dp[0][j] = j;
    // 自底向上求解
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i - 1][j - 1] + 1
                );
            }
        }
    }
    // 储存着整个 s1 和 s2 的最小编辑距离
    return dp[m][n];
}

int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));

2.4 扩展

这里只求出了最小的编辑距离，那具体的操作是什么？其实很简单，代码稍加修改，给 dp 数组增加额外的信息即可：

// int[][] dp;
Node[][] dp;

class Node {
    int val;
    int choice;
    // 0 代表啥都不做
    // 1 代表插入
    // 2 代表删除
    // 3 代表替换
}

val 属性就是之前的 dp 数组的数值，choice 属性代表操作。在做最优选择时，顺便把操作记录下来，然后就从结果反推具体操作。