72. 编辑距离

发表于 分类于 阅读次数： Waline： 本文字数： 1.5k 阅读时长 ≈ 5 分钟

考点

  • LCS

思路

1. 问题定义

给定两个字符串 \(A=\texttt{word1}\)、\(B=\texttt{word2}\)。允许三种操作，每次操作代价为 1：

  1. 插入一个字符（Insert）
  2. 删除一个字符（Delete）
  3. 替换一个字符（Replace）

目标：求将 \(A\) 转换为 \(B\) 的最小操作次数，即编辑距离（Levenshtein distance）。

2. 状态设计（二维前缀 DP）

设 \(n_1 = |A|\)，\(n_2 = |B|\)。

定义状态： \[ f[i][j] = \text{将 } A[0..i-1] \text{ 转换成 } B[0..j-1] \text{ 的最小操作数} \] 其中 \(i \in [0,n_1]\)，\(j \in [0,n_2]\)。 该定义的关键点在于：状态描述的是两个前缀已经完全对齐后的最优代价（完成态），而不是某个“中间字符串”的真实形态。

3. 初始值（边界条件）

3.1 空串到空串

\[ f[0][0] = 0 \]

3.2 将非空前缀变为空串：只能删除

\[ f[i][0] = i \quad (1 \le i \le n_1) \]

因为把 \(A[0..i-1]\) 变成空串只能删除全部 \(i\) 个字符。

3.3 将空串变为非空前缀：只能插入

\[ f[0][j] = j \quad (1 \le j \le n_2) \]

因为从空串得到 \(B[0..j-1]\) 只能插入 \(j\) 个字符。

4. 状态转移方程（核心）

考虑 \(f[i][j]\)（\(i\ge 1, j\ge 1\)），只需要关注最后一位字符：

  • \(A[i-1]\) —— 当前 \(A\) 前缀的最后字符
  • \(B[j-1]\) —— 当前 \(B\) 前缀的最后字符

4.1 若最后字符相等

若 \(A[i-1] = B[j-1]\)，最后一位无需操作： \[ f[i][j] = f[i-1][j-1] \]

4.2 若最后字符不相等

若 \(A[i-1] \ne B[j-1]\)，最后一步必须执行一次操作（+1），且只有三种选择：

  1. 删除 \(A[i-1]\)： 将 \(A[0..i-2]\) 变为 \(B[0..j-1]\) \[ f[i][j] \leftarrow f[i-1][j] + 1 \]

  2. 插入 \(B[j-1]\)： 将 \(A[0..i-1]\) 变为 \(B[0..j-2]\)，再插入一个字符使末位对齐 \[ f[i][j] \leftarrow f[i][j-1] + 1 \]

  3. 替换 \(A[i-1]\to B[j-1]\)： 将 \(A[0..i-2]\) 变为 \(B[0..j-2]\)，再替换末位 \[ f[i][j] \leftarrow f[i-1][j-1] + 1 \]

综合取最小值： \[ f[i][j] = 1 + \min\bigl(f[i-1][j],\ f[i][j-1],\ f[i-1][j-1]\bigr) \quad \text{当 } A[i-1]\ne B[j-1] \]

5. 最终答案位置

完整字符串对应的前缀是 \(A[0..n_1-1]\)、\(B[0..n_2-1]\)，因此答案为： \[ \boxed{f[n_1][n_2]} \]

6. 为什么“插入”在 DP 里只能用“从后面插”来建模？

这一点的关键在于：状态 \(f[i][j]\) 的语义是“两个前缀完全对齐后的最优代价”。因此每一次转移都必须满足一个不变式：

从某个前缀对齐态转移到另一个前缀对齐态时， 下标 \(i, j\) 的变化必须精确对应“处理了哪些前缀字符”。

6.1 “插入”为什么对应 \(f[i][j-1] + 1\)？

若把最后一步设为“插入”，其含义是： 为了得到目标前缀 \(B[0..j-1]\)，最后一个字符 \(B[j-1]\) 是新增出来的。 则插入之前，目标应当还只有 \(B[0..j-2]\)，源仍为 \(A[0..i-1]\)： \[ A[0..i-1] \to B[0..j-2] \quad \text{然后插入 } B[j-1] \] 因此插入的前驱状态必然是 \(f[i][j-1]\)。

6.2 为什么不能把“前面插入”当成独立转移？

若试图把操作解释为“在前面插入一个字符”，那么会导致源串前缀的字符整体右移： 原来第 \(k\) 个字符的相对位置被改变，进而出现“已经对齐的前缀被打乱”的现象。

在 \(f[i][j]\) 的语义下，前缀 \(A[0..i-1]\) 被视为一个固定集合（并以其原始顺序为准）。 “前插”会在过程层面改变对齐关系，从而产生一种难以用 \((i,j)\) 表示的“中间态”： 它既不是 \(A\) 的前 \(i\) 个字符，也不是前 \(i+1\) 个字符的对齐完成态。

换言之：

  • DP 转移要求：前驱状态必须仍然是一个合法的前缀状态
  • “前面插入”会破坏“前缀对齐已完成”的不变式，无法映射为单一的 \(f[\cdot][\cdot]\) 状态

因此，在该前缀 DP 建模下，“插入”只能以“补齐目标前缀的最后一个字符”的形式出现，也即： \[ f[i][j] \leftarrow f[i][j-1] + 1 \] 这并非对真实操作位置的限制，而是对状态建模一致性的限制：只有“末尾补齐”才能保持 dp 下标语义不被破坏。

7. 复杂度

  • 二维 DP：时间 \(O(n_1 n_2)\)，空间 \(O(n_1 n_2)\)
  • 滚动数组：时间 \(O(n_1 n_2)\)，空间 \(O(n_2)\)

8. 参考代码与注释

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
39
40
41
42
43
class Solution {
public:
    static const int maxn = 5e2 + 5;

    int minDistance(string word1, string word2) {
        // f[i][j]：word1 的前 i 个字符 -> word2 的前 j 个字符 的最小编辑距离
        int f[maxn][maxn];

        int n1 = word1.size(), n2 = word2.size();

        // 边界：空串 -> 空串
        f[0][0] = 0;

        // 边界：word1 前 i 个 -> 空串，只能删除 i 次
        for (int i = 1; i <= n1; ++i)
            f[i][0] = i;

        // 边界：空串 -> word2 前 j 个，只能插入 j 次
        for (int j = 1; j <= n2; ++j)
            f[0][j] = j;

        // 填表：按 i 从小到大、j 从小到大，确保转移依赖已计算
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {

                // 若当前末位字符相同，不需要操作，继承左上角
                if (word1[i - 1] == word2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    // 否则三选一（+1）：
                    // 1) 替换：f[i-1][j-1] + 1
                    // 2) 删除：f[i-1][j]   + 1
                    // 3) 插入：f[i][j-1]   + 1
                    f[i][j] = min(f[i - 1][j - 1],
                                  min(f[i - 1][j], f[i][j - 1])) + 1;
                }
            }
        }

        // 答案：完整前缀到完整前缀
        return f[n1][n2];
    }
};

滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static const int maxn = 5e2 + 5;
    int minDistance(string word1, string word2) {
        int f[2][maxn], n1 = word1.size(), n2 = word2.size();
        f[0][0] = 0;
        for (int i = 1; i <= n2; ++i)
            f[0][i] = i;
        for (int i = 1; i <= n1; ++i) {
            f[i & 1][0] = i;
            for (int j = 1; j <= n2; ++j) {
                if (word1[i - 1] == word2[j - 1])
                    f[i & 1][j] = f[i - 1 & 1][j - 1];
                else {
                    f[i & 1][j] = min(f[i - 1 & 1][j - 1],
                                      min(f[i - 1 & 1][j], f[i & 1][j - 1])) +
                                  1;
                }
            }
        }
        return f[n1 & 1][n2];
    }
};