两个字符串的删除操作 图解题解

这道题到底在问什么

word1

"sea"

word2

"eat"

输出

2

解释

sea 删掉 s 变 ea，eat 删掉 t 变 ea，两步后都成 "ea"

先想最直接的笨办法

如果硬枚举「这个字符删不删」，两个单词加起来 n 个字符就有 2ⁿ 种删法，根本算不过来。得换个角度：与其想删什么，不如想留什么。（动画第 3 步）

最优解：一步一步想明白

1. 3如果硬枚举「这个字符删不删」，两个单词加起来 n 个字符就有 2ⁿ 种删法，根本算不过来。得换个角度：与其想删什么，不如想留什么。
2. 4不管怎么删，最后两边剩下的是同一个串，它必然同时是 word1 和 word2 的子序列。想删得最少，就要让这个公共部分尽量长——这正是「最长公共子序列(LCS)」。
3. 5word1 长 m，要删到只剩公共部分得删 m−L 个；word2 长 n，删 n−L 个。两边相加 = m + n − 2L。问题就缩成一句话：求出最长公共子序列长度 L。
4. 6找它们的最长公共子序列上行是 word1="sea"，下行是 word2="eat"。肉眼能看出公共子序列是 "ea"(在两串里都按顺序出现)，长度 2。下面用 DP 表把这个 2 一格一格算出来。
5. 7我们开一张 (m+1)×(n+1) 的表。dp[i][j] 表示：只看 word1 的前 i 个字母、word2 的前 j 个字母，它们最长的公共子序列有多长。多出来的第 0 行第 0 列表示「空串」，方便起步。
6. 8看 word1 第 i 个、word2 第 j 个字母：相等就把这对配进公共子序列，长度 = 左上角 +1;不等就只能从「丢掉其中一个字母」的两种局面里挑更长的——也就是上方和左方取大。
7. 9整张表待填这是 4×4 的 dp 表。最上一行、最左一列的表头是两个单词的字母，ε 是空串占位。每个格子 dp[i][j] 等会儿都会填上一个数。先把地基(第 0 行、第 0 列)铺好。
8. 10空串 vs 空串 = 0先填最左上角 dp[0][0]:两边都取空串(ε)，公共子序列长度自然是 0。这是整张表的起点。
9. 11空串 vs "e" = 0第 0 行代表「word1 是空串」。空串和 "e" 比，没有公共字符，0。继续往右填。
10. 12空串 vs 任何前缀 = 0第 0 行剩下两格同理填 0——空串和「ea」「eat」都没有公共字符。整条第 0 行铺好了。
11. 13"s" vs 空串 = 0再填第 0 列「word2 是空串」的情形:"s" 和空串比，0。这一列也得全是 0。
12. 14任何前缀 vs 空串 = 0第 0 列剩下两格也填 0。地基(第 0 行 + 第 0 列)全部铺完，接下来从左上角的内部格子开始，一行一行往下填真正的值。
13. 15字符不等 → 取上、左较大比 word1 的 s 和 word2 的 e:不相等。那就看「去掉 s」(上方格)和「去掉 e」(左方格)谁的 LCS 长，两个都是 0，所以 dp[1][1]=0。
14. 16字符不等 → 取上、左较大s 和 a 也不等，上方 0、左方 0，取大还是 0。「sea 的前 1 个」和「eat 的前 2 个」之间没有公共字母，合理。
15. 17字符不等 → 取上、左较大s 跟 t 还是不等，结果 0。第一行(只含 word1 的 s)填完——s 不在 "eat" 里出现，整行都是 0。下面第二行才开始热闹。
16. 18字符相等 → 左上角 +1第一次配对成功!word1 的 e 撞上 word2 的 e。把这对 e 接进公共子序列:取左上角 dp[1][0]=0 再 +1 = 1。公共子序列冒出第一个字母。
17. 19字符不等 → 取上、左较大e 和 a 不等。看上方 0 和左方 1:左边那个 1 是刚配好的 e，得保留它。取大 → dp[2][2]=1。已有的公共部分不能丢。
18. 20字符不等 → 取上、左较大e 跟 t 不等，继续从上(0)和左(1)取大 = 1。第二行填完:"se" 和 "eat" 的最长公共子序列长度是 1(就是那个 e)。
19. 21字符不等 → 取上、左较大进第三行,word1 的 a 比 word2 的 e:不等。上方是 1(含那个 e)、左方 0,取大 = 1。把前面 e 的成果继承下来。
20. 22字符相等 → 左上角 +1第二次配对成功!word1 的 a 撞上 word2 的 a。左上角 dp[2][1]=1(那里已经攒了一个 e)再 +1 = 2。公共子序列长成了 "ea"!
21. 23字符不等 → 取上、左较大最后一格:a 跟 t 不等,上方 1、左方 2,取大 = 2。右下角填好,整张表完工。
22. 24L = dp[3][3] = 2表格右下角 dp[3][3]=2 就是最长公共子序列长度 L。下面回溯一下,看这个 2 是哪两个字母配出来的。
23. 25两次 +1 的格子串起公共子序列回溯两次「左上角 +1」发生的格子:dp[2][1] 配出 e、dp[3][2] 配出 a,串起来正是 "ea"。和一开始肉眼看到的公共子序列对上了。
24. 26套上公式:word1 删 m−L=3−2=1 个(删 s),word2 删 n−L=3−2=1 个(删 t),共 2 步。两边都剩 "ea"。和题目示例的输出 2 完全对上!
25. 27左:word1 要删 1 个 · 右:word2 要删 1 个把删除量画成柱子:word1 删 1 个 + word2 删 1 个 = 总共 2 次删除。本质上,每个不在公共子序列里的字母都得删掉,两边加起来就是答案。
26. 28不再去试所有删法,而是填一张 m×n 的表,每格只看左、上、左上三个邻居,一次填好不回头。指数级直接降到多项式级。
27. 31公共子序列那 L 个字符在两个单词里各出现一次,都要保留。所以 word1 删 (m−L)、word2 删 (n−L),L 被减了两次——一边一次。
28. 33若要求连续,e 后接 a 必须紧邻如果误用「公共子串」的转移(不等就归 0),表里 e 和 a 各自孤立成 1,连不起来,会得出错误的删除步数。本题要的是 子序列:e 和 a 在两串里都按顺序出现,哪怕中间隔着别的字母也算数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def minDistance(self, word1, word2):
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]   # dp[i][j]=LCS
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1     # 相等 +1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 取大
        lcs = dp[m][n]
        return m + n - 2 * lcs              # 删除步数

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;   // 相等 +1
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        int lcs = dp[m][n];
        return m + n - 2 * lcs;            // 删除步数
    }
};

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];        // dp[i][j]=LCS
        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;   // 相等 +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;            // 删除步数
    }
}

复杂度

面试官可能追问