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

两个单词删到相同，最少删几个字符

给两个单词 word1 和 word2，每步能从任意一个里删掉一个字符，问最少删几次能让它们完全相同。例子 word1="sea"、word2="eat" 答案 2：sea 删开头的 s、eat 删结尾的 t，两步后都剩 "ea"。

为什么挨个试「删不删」根本试不完

最直接的想法是对每个字符试「删还是不删」。两串共 m+n 个字符、每个两种选择，就有 2^(m+n) 种删法（大 O 记号里叫指数级），字符稍多就枚举不完，且前半截大量重叠被反复重算。

为什么删到只剩公共子序列最省，答案又为何是 m+n−2L

不管怎么删，两串最后剩的是同一个串，它同时是 word1 和 word2 的子序列（按原顺序挑字符、允许中间跳过）。想删得最少，就让这个公共串尽量长，即求最长公共子序列（英文缩写 LCS）。

设 LCS 长度为 L。word1 有 m 个字符、删到只剩 L 个要删 m−L 个，word2 有 n 个要删 n−L 个，相加得删除数 = m+n−2L。L 减两次，因为那 L 个公共字符两串各留一份。求出 L 即可。

dp 表怎么填，字母相等和不等分别接哪个邻居

开一张 (m+1)×(n+1) 的表，dp[i][j] 表示只看 word1 前 i 个、word2 前 j 个字母时公共子序列最长多少。第 0 行列代表空串全填 0，方便起步。

填 dp[i][j] 时比较 word1 第 i 个和 word2 第 j 个字母（下标 word1[i−1]、word2[j−1]，比 dp 表错开一位）。相等就把这对接进公共子序列，长度 = 左上角 dp[i−1][j−1] 加 1；不等就配不上，只能丢掉其中一个字母，取上方 dp[i−1][j]、左方 dp[i][j−1] 中较大的。

拿 "sea" 和 "eat" 亲手把整张表填一遍

m=n=3，第 0 行列全 0。第一行 s 与 e、a、t 都不等取上左大值全 0。第二行 e 撞 word2 的 e，左上角 0 加 1 得 dp[2][1]=1；往右 e 和 a、t 不等取左边 1，dp[2][2]=dp[2][3]=1。第三行 a 和 e 不等取上方 1 得 dp[3][1]=1；a 撞 a，左上角 dp[2][1]=1 加 1 得 dp[3][2]=2，公共子序列长成 "ea"；末格 a 和 t 不等取上方 1、左方 2 得 dp[3][3]=2。

右下角 dp[3][3]=2 就是 L。代回公式，答案 = m+n−2L = 3+3−2×2 = 2，和题目输出对上：word1 删 s、word2 删 t，各 1 个。

填满这张表要多久，子序列可别当成子串

表有 (m+1)×(n+1) 格、每格一次比较取值，时间 O(m×n)；二维表占 O(m×n) 空间，又因每格只看上一行和本行左边，可用滚动数组（只留最近一两行、循环覆盖旧值）把空间压到 O(n)。

两个坑最常见。一是把子序列求成最长公共子串——子串要连续、子序列顺序对即可跳过，转移不同，当子串会算出更小的公共长度、删除步数偏大。二是答案写成 m+n−L：漏一个 L，公共部分两边各留一份要减两次。

Python

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              # 删除步数

C++

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;            // 删除步数
    }
};

Java

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;            // 删除步数
    }
}