两个字符串的删除操作

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

不管怎么删，最后两边剩下的是同一个串，它必然同时是 word1 和 word2 的子序列。想删得最少，就要让这个公共部分尽量长——这正是「最长公共子序列(LCS)」。

word1 长 m，要删到只剩公共部分得删 m−L 个；word2 长 n，删 n−L 个。两边相加 = m + n − 2L。问题就缩成一句话：求出最长公共子序列长度 L。

两个单词排开看：上行是 word1="sea"，下行是 word2="eat"。肉眼能看出公共子序列是 "ea"(在两串里都按顺序出现)，长度 2。下面用 DP 表把这个 2 一格一格算出来。

我们开一张 (m+1)×(n+1) 的表。dp[i][j] 表示：只看 word1 的前 i 个字母、word2 的前 j 个字母，它们最长的公共子序列有多长。多出来的第 0 行第 0 列表示「空串」，方便起步。

看 word1 第 i 个、word2 第 j 个字母：相等就把这对配进公共子序列，长度 = 左上角 +1;不等就只能从「丢掉其中一个字母」的两种局面里挑更长的——也就是上方和左方取大。

建表 · 行=word1，列=word2：这是 4×4 的 dp 表。最上一行、最左一列的表头是两个单词的字母，ε 是空串占位。每个格子 dp[i][j] 等会儿都会填上一个数。先把地基(第 0 行、第 0 列)铺好。

地基 · 角上 dp[0][0]：先填最左上角 dp[0][0]:两边都取空串(ε)，公共子序列长度自然是 0。这是整张表的起点。

地基 · 第 0 行(word1 空) → e：第 0 行代表「word1 是空串」。空串和 "e" 比，没有公共字符，0。继续往右填。

地基 · 第 0 行 → ea / eat：第 0 行剩下两格同理填 0——空串和「ea」「eat」都没有公共字符。整条第 0 行铺好了。

地基 · 第 0 列(word2 空) → s：再填第 0 列「word2 是空串」的情形:"s" 和空串比，0。这一列也得全是 0。

地基 · 第 0 列 → se / sea：第 0 列剩下两格也填 0。地基(第 0 行 + 第 0 列)全部铺完，接下来从左上角的内部格子开始，一行一行往下填真正的值。

填 dp[1][1] · s vs e：比 word1 的 s 和 word2 的 e:不相等。那就看「去掉 s」(上方格)和「去掉 e」(左方格)谁的 LCS 长，两个都是 0，所以 dp[1][1]=0。

填 dp[1][2] · s vs a：s 和 a 也不等，上方 0、左方 0，取大还是 0。「sea 的前 1 个」和「eat 的前 2 个」之间没有公共字母，合理。

填 dp[1][3] · s vs t：s 跟 t 还是不等，结果 0。第一行(只含 word1 的 s)填完——s 不在 "eat" 里出现，整行都是 0。下面第二行才开始热闹。

填 dp[2][1] · e vs e ✓：第一次配对成功!word1 的 e 撞上 word2 的 e。把这对 e 接进公共子序列:取左上角 dp[1][0]=0 再 +1 = 1。公共子序列冒出第一个字母。

填 dp[2][2] · e vs a：e 和 a 不等。看上方 0 和左方 1:左边那个 1 是刚配好的 e，得保留它。取大 → dp[2][2]=1。已有的公共部分不能丢。

填 dp[2][3] · e vs t：e 跟 t 不等，继续从上(0)和左(1)取大 = 1。第二行填完:"se" 和 "eat" 的最长公共子序列长度是 1(就是那个 e)。

填 dp[3][1] · a vs e：进第三行,word1 的 a 比 word2 的 e:不等。上方是 1(含那个 e)、左方 0,取大 = 1。把前面 e 的成果继承下来。

填 dp[3][2] · a vs a ✓：第二次配对成功!word1 的 a 撞上 word2 的 a。左上角 dp[2][1]=1(那里已经攒了一个 e)再 +1 = 2。公共子序列长成了 "ea"!

填 dp[3][3] · a vs t · 最后一格：最后一格:a 跟 t 不等,上方 1、左方 2,取大 = 2。右下角填好,整张表完工。

读结果 · 右下角就是 LCS：表格右下角 dp[3][3]=2 就是最长公共子序列长度 L。下面回溯一下,看这个 2 是哪两个字母配出来的。

回溯路径 · 点亮 "ea"：回溯两次「左上角 +1」发生的格子:dp[2][1] 配出 e、dp[3][2] 配出 a,串起来正是 "ea"。和一开始肉眼看到的公共子序列对上了。

套上公式:word1 删 m−L=3−2=1 个(删 s),word2 删 n−L=3−2=1 个(删 t),共 2 步。两边都剩 "ea"。和题目示例的输出 2 完全对上!

删除步数怎么来的：把删除量画成柱子:word1 删 1 个 + word2 删 1 个 = 总共 2 次删除。本质上,每个不在公共子序列里的字母都得删掉,两边加起来就是答案。

不再去试所有删法,而是填一张 m×n 的表,每格只看左、上、左上三个邻居,一次填好不回头。指数级直接降到多项式级。

公共子序列那 L 个字符在两个单词里各出现一次,都要保留。所以 word1 删 (m−L)、word2 删 (n−L),L 被减了两次——一边一次。

雷区实演 · 误当公共子串：如果误用「公共子串」的转移(不等就归 0),表里 e 和 a 各自孤立成 1,连不起来,会得出错误的删除步数。本题要的是 子序列:e 和 a 在两串里都按顺序出现,哪怕中间隔着别的字母也算数。

边界三连：空串的情形最能验脑子里的公式:LCS=0 时答案 = m+n−0 = 两串总长,意味着全删光,完全合理。

面试追问：把它和编辑距离串起来讲——「只允许删 = LCS 变体」,再补一句直接 DP 删除数的写法,是这题的加分点。