两个字符串的删除操作：删到只剩最长公共子序列
只能删。最终相等的那串必须同时是两边的子序列。留得越长删得越少，删除数 = m + n − 2·LCS。
按 LC1143 填 LCS：相等则左上 +1，不等取上/左较大。答案是 len(A)+len(B)−2·lcs[m][n]，即两边各自删掉非公共部分。时间 O(m·n)，空间 O(m·n)。
这是 LeetCode 583. Delete Operation for Two Strings。两个单词 word1、word2，每一步可以删掉任一单词中的一个字符，使两个单词相等，求最少删除次数。不能插入，不能替换。
主例 word1 = "sea"，word2 = "eat"。两边都删到 "ea"：sea 删 s，eat 删 t，共 2 次。演示表右下角 LCS=2，换算 (3−2)+(3−2)=2。
第一直觉是对齐后一个个删不同的字符。"sea" 和 "eat" 对位全不同，会以为要删 6 次。缺的是：留下的公共部分可以不连续、可以不对齐到同一下标。下面从这块缺口把它收成 LCS。
最少删除 = 两边长度减去两倍 LCS
删完之后两个串变成同一个串 t。t 的每个字符都来自 word1 的某次保留，也来自 word2 的某次保留，相对顺序不变。所以 t 必须同时是两者的子序列。删除次数 = (m−|t|)+(n−|t|)。|t| 越大，删除越少。最大的 |t| 就是 LCS 长度。
缺的不是「怎么删」，而是「最多能留多长」。直接对删除次数做 DP 也行：dp[i][j] 表示两个前缀变成相等的最少删除，相等则继承左上，不等则删 A 尾或删 B 尾加一。它和 LCS 互为镜像：最少删除 = m+n−2·LCS。先算 LCS 更短、也和 LC1143 同一张表。
从缺口套 LCS。空前缀对空前缀长度为 0。A[i−1]==B[j−1] 时 lcs[i][j]=lcs[i−1][j−1]+1，否则取 max(上, 左)。填完右下角，代入 m+n−2·LCS。
用手走主例。演示给出填完的表：空前缀一行全 0；三行数据是 [0,1,1,1]、[0,1,1,1]、[0,1,1,2]，光标在右下角。右下角 2 就是 LCS 长度，对应 ea。sea 去掉 s，eat 去掉 t，删除数 (3−2)+(3−2)=2。相等走左上加一、不等取上或左，填到这个 2 为止。
两个串相等则 LCS=m，删除 0。一个为空则必须删光另一个，答案是另一个的长度，此时 LCS=0。LC72 多了替换，转移多一种「改尾」；本题没有，不要把替换算进去。
留公共，不是对位删对位比较会把 sea 和 eat 看成三个都不同。LCS 允许跳过 s 和 t，只留 ea。删除数只跟「没留下的字符」有关。
| "" | e | a | t | |
|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 |
| s | 0 | 1 | 1 | 1 |
| e | 0 | 1 | 1 | 1 |
| a | 0 | 1 | 1 | 2 |
Go：LCS + 换算
func minDistance(a, b string) int {m, n := len(a), len(b)lcs := make([][]int, m+1)for i := 0; i <= m; i++ { lcs[i] = make([]int, n+1) }for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if a[i-1] == b[j-1] {lcs[i][j] = lcs[i-1][j-1] + 1} else {lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])}}}return m + n - 2*lcs[m][n]}func max(a, b int) int { if a > b { return a }; return b }
1表的填法和 LC1143 相同。相等走左上加一，不等取更大的一边。
2主例右下角 2，对应 ea。不要在这里返回 2，那是长度不是删除数。
3m+n−2*LCS 把两边各自多出来的字符一次算清。3+3−4=2。
总结
只能删，就尽量留 LCS。主例 sea 与 eat 留 ea，删除 2 次。
- 最终相等串必须是公共子序列。对位删会把主例错成 6。
- 删除数 = m+n−2·LCS，和「对删除次数直接 DP」等价。
- LC72 多了替换；本题转移里没有改字符这一支。