583. 两个字符串的删除操作

发表于 分类于 阅读次数： Waline： 本文字数： 654 阅读时长 ≈ 2 分钟

考点

  • LCS

思路

1. 问题概述

给定两个字符串 word1 与 word2，每次操作允许删除任意一个字符串中的一个字符。目标是用最少操作次数，使两个字符串变得完全相同。

该问题本质是一个典型二维动态规划：只允许删除，因此状态设计会落在“把前缀变成相同”这一类。

2. 状态定义（DP 含义）

设： \[ f[i][j] \] 表示：将 word1 的前 \(i\) 个字符（word1[0..i-1]）与 word2 的前 \(j\) 个字符（word2[0..j-1]）通过仅删除操作变为相同字符串所需的最少删除次数。

3. 初始值设计（边界条件）

3.1 空串与空串

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

空串和空串已经相同，不需要删除。

3.2 word2 为空串

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

要让 word1 的前 \(i\) 个字符与空串相同，只能把这 \(i\) 个字符全部删掉。

3.3 word1 为空串

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

同理，要让空串与 word2 前 \(j\) 个字符相同，只能删除 word2 的这 \(j\) 个字符。

这些初始化直接对应代码中的两条边界赋值循环。

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

考虑 \(f[i][j]\)，观察 word1[i-1] 与 word2[j-1]（即两个前缀的最后一个字符）。

4.1 末尾字符相同

如果： \[ word1[i-1] = word2[j-1] \] 那么这两个字符可以都保留，不需要额外删除，问题缩小为更短前缀： \[ f[i][j] = f[i-1][j-1] \]

4.2 末尾字符不同

如果： \[ word1[i-1] \ne word2[j-1] \] 由于只能删除，想让两前缀相同，最后一步只能二选一：

  • 删除 word1 的最后一个字符：代价 \(f[i-1][j] + 1\)
  • 删除 word2 的最后一个字符：代价 \(f[i][j-1] + 1\)

取更小者： \[ f[i][j] = \min\bigl(f[i-1][j],\, f[i][j-1]\bigr) + 1 \]

5. 答案与输出

目标是让完整字符串相同，因此答案为： \[ f[n_1][n_2] \] 其中 \(n_1 = |word1|\)，\(n_2 = |word2|\)。

6. 复杂度分析

  • 时间复杂度：\(\mathcal{O}(n_1 \cdot n_2)\)，每个状态计算 \(O(1)\)
  • 空间复杂度：\(\mathcal{O}(n_1 \cdot n_2)\)，存储整张 DP 表

7. AC代码

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