LeetCode 583. 两个字符串的删除操作
目录
题目描述
题意分析
给两个字符串
word1、word2，每一步可以从任意一个字符串里删掉一个字符，问最少删几步能让两个字符串变得完全相同。返回的是步数，不是最终字符串。
先把「操作」这个动态过程静态化。只允许删除、不允许插入或替换，意味着两个字符串都只能变短，而且任何一个删剩下的结果一定是它自己的子序列。既然最后两边要相等，那么剩下的那个串必须同时是
word1的子序列和word2的子序列，也就是它们的一个公共子序列。反过来，任取一个公共子序列，都可以通过删掉两边多余的字符达成，所以「可达的最终串」与「公共子序列」是一一对应的。
再看代价。若最终保留的公共子序列长度为
k，那么word1要删m - k个字符、word2要删n - k个字符，总步数m + n - 2k。这个式子对k单调递减，所以保留得越长越好——问题就变成了求最长公共子序列的长度。
数据范围里两个串长度都不超过 500，$O(mn) = 2.5 \times 10^5$ 的二维表完全可以承受，这个规模明显是在鼓励双序列的表格型递推，而不是指数级枚举。
边界：某个字符串可能为空，此时只能把另一个全删光，答案是另一个的长度；两个串可能完全相同，答案为 0；两个串可能一个公共字符都没有，答案是
m + n。
解法：最长公共子序列 DP
核心思路
暴力做法是枚举
word1的所有子序列，逐个检查是不是word2的子序列，取最长的那个，复杂度 $O(2^m \cdot n)$，m = 500时不可能。瓶颈在于大量子序列做了重复的匹配工作：判断「word1的前i个字符」和「word2的前j个字符」能匹配多长，这件事被反复重算。
观察点是：一个公共子序列的构造过程可以按「两个串各自的前缀」来组织。考虑
word1[i-1]和word2[j-1]这两个末尾字符，只有两种情形——它们相等，那么把它俩配成一对必然不亏（配上去长度加一，剩下的问题缩成两个更短的前缀）；它们不等，那么这两个字符至少有一个不可能出现在最终配对里，于是问题一定能归约成「丢掉word1末尾」或「丢掉word2末尾」中的某一种。两种情形都把大问题化成了规模更小、形状相同的子问题，且子问题只依赖前缀——这正是二维递推的信号。
状态定义写清楚：
dp[i][j]表示word1的前i个字符与word2的前j个字符的最长公共子序列长度。 注意i、j是长度不是下标，所以取值范围是0..m和0..n，访问原串字符时要用i - 1、j - 1。用长度而非下标做维度，是为了让「空前缀」有一个天然的表示。
转移分两支。
word1[i-1] == word2[j-1]时dp[i][j] = dp[i-1][j-1] + 1：末尾这对字符可以直接接到「双方都去掉末尾」的最优解后面。这里可以证明不必再和另外两项取最大值——把末尾这对配起来永远不比不配差。word1[i-1] != word2[j-1]时dp[i][j] = max(dp[i-1][j], dp[i][j-1])：末尾两个字符不能互相匹配，所以至少要放弃其中一个，两种放弃方式取更优者。
边界是
dp[0][j] = dp[i][0] = 0：空串和任何串的公共子序列长度都是 0。Java 和 Go 的数组默认零值恰好就是它，不需要显式初始化。
最后按前面推出的式子返回
m + n - 2 * dp[m][n]。
解题步骤
- 取出
m、n，开(m + 1) × (n + 1)的二维数组dp：多出来的第 0 行第 0 列专门表示空前缀，有了它转移里就不必对i == 1或j == 1做特判，dp[i-1][j-1]永远合法。- 不做额外初始化：全 0 的默认值就是正确的边界条件，多写一遍反而容易写错。
- 双层循环
i从 1 到m、j从 1 到n，都取到等号：i、j是长度，m、n是最大长度，必须包含在内，否则最后一个字符永远参与不了转移。循环顺序保证读dp[i-1][*]和dp[i][j-1]时它们都已经算好——这就是「每个状态只依赖已确定状态」的落实。- 比较
word1.charAt(i - 1)与word2.charAt(j - 1)：这里的减一是长度到下标的换算，漏掉就会越界或比错字符。- 相等分支写
dp[i-1][j-1] + 1：只能从对角线来。若误写成dp[i-1][j] + 1或dp[i][j-1] + 1，等于允许同一个字符被匹配两次。- 不等分支写
max(dp[i-1][j], dp[i][j-1])：两项分别对应「不要word1的第i个字符」和「不要word2的第j个字符」。不需要再取dp[i-1][j-1]，因为它必然不大于这两者中的任意一个。- 返回
m + n - 2 * dp[m][n]：dp[m][n]是两个完整串的 LCS 长度，每保留一个公共字符就同时省下两次删除，所以乘 2。
以
word1 = "sea"、word2 = "eat"走一遍（期望答案 2："sea"删s、"eat"删t，都变成"ea"）。
m = 3、n = 3，dp是 4×4 的全零表，行下标i对应"sea"的前缀，列下标j对应"eat"的前缀。
i = 1（前缀"s"）：j = 1比较's'与'e'，不等，dp[1][1] = max(dp[0][1], dp[1][0]) = 0；j = 2比较's'与'a'，不等，仍为 0；j = 3比较's'与't'，不等，仍为 0。第 1 行是[0, 0, 0, 0]——"s"和"eat"没有公共字符。
i = 2（前缀"se"）：j = 1比较'e'与'e'，相等，dp[2][1] = dp[1][0] + 1 = 1；j = 2比较'e'与'a'，不等，max(dp[1][2], dp[2][1]) = max(0, 1) = 1；j = 3比较'e'与't'，不等，max(dp[1][3], dp[2][2]) = max(0, 1) = 1。第 2 行是[0, 1, 1, 1]。
i = 3（前缀"sea"）：j = 1比较'a'与'e'，不等，max(dp[2][1], dp[3][0]) = max(1, 0) = 1；j = 2比较'a'与'a'，相等，dp[3][2] = dp[2][1] + 1 = 2；j = 3比较'a'与't'，不等，max(dp[2][3], dp[3][2]) = max(1, 2) = 2。第 3 行是[0, 1, 2, 2]。
dp[3][3] = 2，对应公共子序列"ea"。返回3 + 3 - 2 × 2 = 2。
顺带看一个空串边界
word1 = ""、word2 = "abc"：双层循环因为m = 0一次都不进，dp[0][3]保持 0，返回0 + 3 - 0 = 3，正是把word2全删光的步数，主逻辑天然覆盖。
代码实现
class Solution {
// 为了删除次数最少，应当保留最长公共子序列，设长度为 lcs，答案就是 m + n - 2 * lcs。
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int lcs = dp[m][n];
return m + n - 2 * lcs;
}
}
func minDistance(word1 string, word2 string) int {
// 为了删除次数最少，应当保留最长公共子序列，设长度为 lcs，答案就是 m + n - 2 * lcs。
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
if dp[i-1][j] > dp[i][j-1] {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
}
lcs := dp[m][n]
return m + n - 2*lcs
}
复杂度分析
- 时间复杂度：$O(mn)$，其中
m、n是两个串的长度。凭什么：状态总数是 $(m+1)(n+1)$，每个状态只做一次字符比较和常数次取最值，没有任何状态被重复计算。- 空间复杂度：$O(mn)$。凭什么：完整保存了整张二维表。由于每行只依赖上一行和本行左侧，可以滚动成两行甚至一行把空间压到 $O(n)$，代价是丢失回溯出具体公共子序列的能力——本题只要长度，压维是安全的。
关键点总结
- 「只允许删除、要求最后相等」等价于「保留一个公共子序列」，把操作序列翻译成最终形态，是这类操作型问题的通用第一步；能说出这个等价关系，比直接背 LCS 模板更能体现分析能力。
- 代价式
m + n - 2k对k单调递减，所以最小化删除次数等价于最大化保留长度——先把目标函数写出来再判断优化方向，可以避免上来就设「删除次数」为状态而把转移写复杂。- 双序列 DP 的维度用「前缀长度」而不是「下标」，是为了让空前缀有位置可放，从而把边界条件变成默认零值，这个小习惯能消掉一大批特判。
- 末尾字符相等时直接取对角线加一、不与另外两项取最值，背后是「配对末尾永不吃亏」的交换论证；面试官追问「为什么不用
max三项」时，这就是标准答案。- 只要长度不要方案时可以滚动压维到 $O(n)$，要还原具体子序列则必须保留完整表格——主动点出这个取舍是加分项。
易错点总结
- 状态定义成「最少删除次数」却用 LCS 的转移式：
word1 = "sea"、word2 = "eat"时相等分支写成dp[i-1][j-1] + 1会把步数越算越大，返回 6 之类的值。dp开成m × n而不是(m+1) × (n+1)：i = 1时访问dp[0][0]尚可，但循环上界改成m - 1后最后一个字符不参与转移，word1 = "a"、word2 = "a"会返回 2 而不是 0。- 比较字符时忘记减一，写成
word1.charAt(i)：i取到m时数组越界，word1 = "sea"直接抛异常。- 相等分支写成
dp[i-1][j] + 1：word1 = "aa"、word2 = "a"会把word2里唯一的'a'匹配两次，dp[2][1]变成 2，返回2 + 1 - 4 = -1这样的负数。- 不等分支漏掉
max，直接写dp[i-1][j]：word1 = "sea"、word2 = "eat"里dp[3][3]会取到 1 而不是 2，返回 4。- 循环从 0 开始且不做偏移：
i = 0时访问dp[-1][-1]，Java 抛越界、Go 直接 panic。- 返回
m + n - dp[m][n]忘记乘 2：word1 = "sea"、word2 = "eat"返回 4 而不是 2，因为每个保留的公共字符实际上省掉了两次删除。- 返回
dp[m][n]本身：word1 = "sea"、word2 = "eat"返回 2 恰好蒙对，但word1 = "abc"、word2 = "abc"会返回 3 而正确答案是 0，这类「碰巧过样例」的错误最难自查。- 压成一维时正序更新且没有暂存左上角的值：
word1 = "abcde"、word2 = "ace"中dp[j-1]已被本行覆盖，相等分支读到的不再是上一行的对角线值，结果偏大。- 对空串输入额外加特判并提前返回错误值：
word1 = ""、word2 = ""时若返回 -1 或抛异常，就破坏了主逻辑本来已经正确覆盖的边界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 本题的内核，直接返回 dp[m][n]，不需要再换算成删除次数 |
| 712. 两个字符串的最小ASCII删除和 | 中等 | 代价从「删一个算一步」变成「按 ASCII 值计费」，不能靠最长保留长度反推 |
| 72. 编辑距离 | 中等 | 多了插入与替换两种操作，转移变成三项取最小，且边界要初始化成 i 和 j
|
| 1035. 不相交的线 | 中等 | 换皮的 LCS，连线不相交等价于匹配保持相对顺序，转移式一字不改 |
| 115. 不同的子序列 | 困难 | 求匹配方案数而非最长长度，转移由取最值改为求和，初值 dp[i][0] = 1
|
| 516. 最长回文子序列 | 中等 | 单串问题，等价于串与其反转串求 LCS，也可直接用区间 DP 从两端向内推 |
| 97. 交错字符串 | 中等 | 双序列表格但状态是布尔可行性，且第三个串的下标由 i + j 隐式确定 |
| 300. 最长递增子序列 | 中等 | 单序列子序列 DP，状态只有一维，转移要回看所有更小的下标 |
| LCR 095. 最长公共子序列 | 中等 | 与 1143 同题，可直接套用 |
| LCR 096. 交错字符串 | 中等 | 与 97 同题，可直接套用 |