LeetCode LCR 095. 最长公共子序列

2026-03-28 HGNULB 约 16 分钟

文章信息 5 个分类 · 3 个标签

分类

LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）

标签

字符串 动态规划 LCR

目录 收起 展开

题目描述

✅ LCR 095. 最长公共子序列

题意分析

输入两个字符串 text1 和 text2，要求返回它们最长公共子序列的长度。子序列的定义是「删掉原串中任意个（含零个）字符、不改变剩余字符相对顺序」得到的串，因此公共子序列不必连续，但必须保序。

「不必连续」和「必须保序」这两条一起把问题钉死了：它不是求公共子串（那要求位置连续），也不是求公共字符的多重集大小（那完全不管顺序）。判断一个思路对不对，最快的办法就是拿 "ab" 和 "ba" 试——它们有两个公共字符，但最长公共子序列只有 1。

题目只要长度，不要求输出具体的子序列，所以不需要记录路径。另一个关键信号是这里同时有两个串：任何时刻都要同时说清「text1 消耗到了哪里」和「text2 消耗到了哪里」，只报其中一个位置无法描述局面，两个进度是互相独立的两个维度。它要求的又是「最长」，说明每一对下标上都存在「用还是不用」的选择，且这些选择之间会互相制约：一旦决定在某两个位置上配对，后面的配对就只能发生在这两个位置之后。

需要单独想清楚的边界：任意一个串为空时答案是 0；两串完全相同时答案是串长；两串没有任何公共字符时答案是 0；同一个字符在串里重复出现是允许的，配对时不能因为「这个字符已经用过」就跳过。

解法一：二维动态规划

核心思路

暴力做法是枚举 text1 的所有子序列，再逐个检查是否也是 text2 的子序列，规模是 $2^m$ 级别，长度稍大就不可行。换成递归的说法：站在两个串的末位上，要么认为这两位配成一对，要么放弃其中一个末位，分支不断裂开且大量重复。

瓶颈就在这些重复上——不同的删除顺序会落到同一对「剩余前缀」上，而后续的最优解只取决于这对前缀，与之前删了谁、按什么顺序删完全无关。这就是可以做状态压缩的信号。

状态定义：dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度，i、j 从 0 开始计数，0 表示空前缀。最终答案是 dp[m][n]。

转移方程的每一项含义：

• 当 text1[i - 1] == text2[j - 1] 时，dp[i][j] = dp[i - 1][j - 1] + 1。这一项的含义是「把这两个相同的末位配成一对，接在两个更短前缀的最优解后面」。加一代表新配的这一对，dp[i - 1][j - 1] 代表配对之前两侧都必须退一格。之所以可以断定「相同的末位一定值得配对」，是因为任何不配对的方案都可以改成配对方案而长度不减：若最优解没有用到这两位，把它的最后一对替换成这两位仍然合法，长度不变；若只用到其中一位，把那一位换成末位配对同样合法。
• 当两个末位不同时，它们不可能同时出现在公共子序列的末尾，因为一个子序列的最后一个字符只有一个值。于是至少有一个末位是多余的，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。第一项表示丢掉 text1 的末位，第二项表示丢掉 text2 的末位，两者取更优。这里不需要第三项 dp[i - 1][j - 1]（同时丢两个），因为它不会超过前两项中的任何一个。

为什么这个状态定义能递推：dp[i][j] 的取值只由「两个前缀各有多长」决定，而每一步决策（配对或丢弃末位）都严格缩短至少一个前缀，因此依赖关系没有环，可以按前缀长度递增的顺序求解。同时它具备最优子结构：把最优公共子序列的最后一对配对拆掉，剩下的部分必然是对应更短前缀的最优解。

循环不变量：外层进入第 i 行前，第 0 到 i - 1 行已全部是最终值；内层进入第 j 列前，本行第 0 到 j - 1 列已是最终值。转移依赖的 (i - 1, j - 1)、(i - 1, j)、(i, j - 1) 都落在这两部分内，所以按 i、j 递增填表是安全的。

第一行和第一列代表空前缀，答案恒为 0，正好等于数组的默认初值，所以这道题连初始化都可以省掉——这是它比编辑距离更容易写对的原因。

解题步骤

• 取 m = text1.length()、n = text2.length()，开一张 (m + 1) x (n + 1) 的表。多出来的一行一列专门表示空前缀，这样边界不用写在循环里。
• 不需要显式初始化：空前缀的答案是 0，与 Java 的 int[][] 和 Go 的 make([]int, ...) 默认值一致。
• 外层 i 从 1 到 m，内层 j 从 1 到 n，保证上面的循环不变量成立。
• 比较 text1.charAt(i - 1) 与 text2.charAt(j - 1)。下标减一是因为 dp 的下标是「前缀长度」而字符下标从 0 开始。
• 相同则取左上角加一，代表新配了一对。
• 不同则取上方和左方的较大值，代表丢掉某一侧的末位；这里绝不能加一。
• 返回 dp[m][n]。

以 text1 = "abcde"、text2 = "ace" 走一遍，这是官方样例，正确答案是 3。表是 6 行 4 列，行下标是 text1 的前缀长度，列下标是 text2 的前缀长度。

第 0 行全是 0：空的 text1 和任何前缀都没有公共子序列。

第 1 行处理 'a'。对 'a' 相同，取 dp[0][0] + 1 = 1；对 'c' 不同，取 max(dp[0][2]=0, dp[1][1]=1) = 1；对 'e' 不同，取 max(dp[0][3]=0, dp[1][2]=1) = 1。整行是 0 1 1 1，含义是 "a" 与 "a"、"ac"、"ace" 的公共子序列都只有 "a"。

第 2 行处理 'b'。'b' 与三个字符都不同，于是逐列取上方与左方的较大值：max(dp[1][1]=1, dp[2][0]=0) = 1、max(dp[1][2]=1, dp[2][1]=1) = 1、max(dp[1][3]=1, dp[2][2]=1) = 1。整行是 0 1 1 1，和上一行一样——因为 'b' 对答案毫无贡献。

第 3 行处理 'c'。对 'a' 不同，max(dp[2][1]=1, 0) = 1；对 'c' 相同，取 dp[2][1] + 1 = 2；对 'e' 不同，max(dp[2][3]=1, dp[3][2]=2) = 2。整行是 0 1 2 2，此时已经配出了 "ac"。

第 4 行处理 'd'。三个字符都不同，逐列取较大值得到 max(dp[3][1]=1, 0) = 1、max(dp[3][2]=2, dp[4][1]=1) = 2、max(dp[3][3]=2, dp[4][2]=2) = 2。整行是 0 1 2 2。

第 5 行处理 'e'。对 'a' 不同得 1；对 'c' 不同，max(dp[4][2]=2, dp[5][1]=1) = 2；对 'e' 相同，取 dp[4][2] + 1 = 3。整行是 0 1 2 3。

返回 dp[5][3] = 3，对应公共子序列 "ace"。

代码实现

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.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]);
                }
            }
        }

        return dp[m][n];
    }
}

func longestCommonSubsequence(text1 string, text2 string) int {
    m := len(text1)
    n := len(text2)
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                // 两个末尾字符相同，可以共同接到更短前缀答案后面。
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[m][n]
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

• 时间复杂度：$O(mn)$。主导项是填表的双重循环，状态数为 (m + 1)(n + 1)，每个状态只做一次字符比较和一次取最大值，没有状态被重复求解。
• 空间复杂度：$O(mn)$。整张二维表是唯一的非常数开销。如果还要输出具体的公共子序列，这张表正是回溯所必需的，此时它不算浪费。

关键点总结

• 双序列问题的通用状态是「两个前缀长度构成的下标对」。只要「后续最优解只取决于剩下多少」，就可以把指数级的删除顺序压成 $O(mn)$ 个状态。
• 转移按「两个末位的关系」分类：相同则配对并双双退格，不同则说明至少有一位多余，分别丢弃再取最优。搞清「加一代表配了一对」这层含义，比背方程可靠得多。
• 「相同就一定配对」需要一句交换论证支撑：任何不配对的最优方案都能改造成配对方案而不变短。这类「贪心选择性质」是很多 DP 能砍掉分支的原因。
• 让边界退化成默认值是一种减少出错的设计。本题空前缀答案恰好是 0，于是初始化整段代码都可以省掉；反过来在编辑距离里边界不是 0，就必须显式写。
• 面试视角：先把状态定义和两条转移用一句话说清，再写代码，面试官最想确认的就是这两句。常见追问是「空间能不能降到一行」和「怎么把这个子序列本身打印出来」，后者答「从 dp[m][n] 沿转移来源回溯，相等时同时退两格并记下字符」。不要把「统计两串公共字符个数」或「排序后取交集」当答案，它们丢掉了顺序约束。

解法二：滚动数组动态规划

核心思路

观察转移，dp[i][j] 只用到第 i - 1 行的两个格子和第 i 行左边一个格子，第 i - 2 行及更早的数据再也不会被读取。既然如此，就没必要保留整张表。

于是把二维表压成长度 n + 1 的一维数组，让同一个下标在不同时刻代表不同行。内层推进到列 j 时的不变量是：dp[0..j - 1] 已经是当前行 i 的值，dp[j..n] 还是上一行 i - 1 的值。

三个来源在一维数组里的落点分别是：左方 dp[i][j - 1] 就是已经更新过的 dp[j - 1]；上方 dp[i - 1][j] 就是即将被覆盖的旧 dp[j]；左上 dp[i - 1][j - 1] 是上一列被覆盖掉的旧值，数组里已经找不到了，必须用一个标量 pre 提前接住。

具体做法是每列先把旧 dp[j] 存进 up，本列算完后执行 pre = up。这两个名字指的是同一个格子 dp[i - 1][j]：对第 j 列它是「上方」，对第 j + 1 列它就成了「左上」。相对位置随 j 前进而改变，值并没有变。

还有两个细节：每行开始必须把 pre 重置为 0，因为新行的「左上起点」是 dp[i - 1][0] = 0，若沿用上一行末尾的 pre，第一列就会凭空多算；而字符不同的分支可以直接写 dp[j] = max(dp[j], dp[j - 1])，因为此刻的 dp[j] 恰好就是上方旧值、dp[j - 1] 恰好就是左方新值，正好对应两个转移来源。

解题步骤

• 建一个长度 n + 1 的数组 dp，全 0。这就是第 0 行，含义是空 text1 与任何前缀都没有公共子序列。
• 外层枚举 text1 的前缀长度 i 从 1 到 m，每一轮把数组从第 i - 1 行原地推进到第 i 行。
• 进入新行时令 pre = 0，代表 dp[i - 1][0]。这一步不能省，否则会带进上一行的残留值。
• 内层 j 从 1 到 n，必须正序：转移要用当前行的 dp[j - 1]，只有正序才能保证它已经更新。
• 每列先 up = dp[j] 保存上方旧值，因为紧接着这个位置就要被覆盖。
• 字符相同则 dp[j] = pre + 1；不同则 dp[j] = max(dp[j], dp[j - 1])，即上方旧值与左方新值取大。
• 本列结束执行 pre = up，把上方旧值交给下一列当左上旧值。顺序不能提前到赋值之后再取 dp[j]，那样拿到的是新值。
• 所有行处理完返回 dp[n]。

以 text1 = "abc"、text2 = "bac" 走一遍，正确答案是 2（"ac" 或 "bc"）。初始 dp = [0, 0, 0, 0]。

第一轮 i = 1，当前字符 'a'，pre = 0。列 1：up = 0，'a' 与 'b' 不同，dp[1] = max(0, dp[0]=0) = 0，pre = 0。列 2：up = 0，'a' 与 'a' 相同，dp[2] = pre + 1 = 1，pre = 0。列 3：up = 0，'a' 与 'c' 不同，dp[3] = max(0, dp[2]=1) = 1，pre = 0。行末 dp = [0, 0, 1, 1]。

第二轮 i = 2，当前字符 'b'，pre 重置为 0。列 1：up = dp[1] = 0，'b' 与 'b' 相同，dp[1] = pre + 1 = 1，pre = 0。列 2：up = dp[2] = 1，'b' 与 'a' 不同，dp[2] = max(1, dp[1]=1) = 1，pre = 1。列 3：up = dp[3] = 1，'b' 与 'c' 不同，dp[3] = max(1, dp[2]=1) = 1，pre = 1。行末 dp = [0, 1, 1, 1]。

第三轮 i = 3，当前字符 'c'，pre 重置为 0。列 1：up = dp[1] = 1，'c' 与 'b' 不同，dp[1] = max(1, dp[0]=0) = 1，pre = 1。列 2：up = dp[2] = 1，'c' 与 'a' 不同，dp[2] = max(1, dp[1]=1) = 1，pre = 1。列 3：up = dp[3] = 1，'c' 与 'c' 相同，dp[3] = pre + 1 = 2。

返回 dp[3] = 2。这里可以看到 pre 的作用：最后一列用的是第二行的 dp[2] = 1，而不是当前行已经被更新成 1 的 dp[2]——两者数值恰好相同，但含义完全不同，遇到数值不同的用例时混用就会出错。

代码实现

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[] dp = new int[n + 1];

        for (int i = 1; i <= m; i++) {
            int pre = 0;
            for (int j = 1; j <= n; j++) {
                int up = dp[j];
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // pre 是二维表里的左上角旧值。
                    dp[j] = pre + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                pre = up;
            }
        }

        return dp[n];
    }
}

func longestCommonSubsequence(text1 string, text2 string) int {
    m := len(text1)
    n := len(text2)
    dp := make([]int, n+1)

    for i := 1; i <= m; i++ {
        pre := 0
        for j := 1; j <= n; j++ {
            up := dp[j]
            if text1[i-1] == text2[j-1] {
                // pre 是二维表里的左上角旧值。
                dp[j] = pre + 1
            } else {
                dp[j] = maxInt(dp[j], dp[j-1])
            }
            pre = up
        }
    }

    return dp[n]
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

• 时间复杂度：$O(mn)$。状态总数没变，压缩只改变存储方式；每个状态仍是常数次操作，两个标量的读写也是常数开销。
• 空间复杂度：$O(n)$。只保留一行状态加 pre、up 两个标量。若在开头把较短的串换到内层维度，可以进一步降到 $O(\min(m, n))$。

关键点总结

• 判断能否用滚动数组，方法是把转移里出现的所有下标列出来，看最远回溯到第几层。只依赖上一层的，都能压成一行。
• 原地覆盖的代价是「同一个下标在不同时刻代表不同状态」。写之前先把不变量写出来——dp[0..j - 1] 属于新层、dp[j..n] 属于旧层——再逐个把转移来源对应过去，比写完再调试快得多。
• 被覆盖掉的旧值用标量在迭代之间传递，是滚动数组的标准补丁。关键是认清「本轮的上方」就是「下轮的左上」，同一个值换个名字继续用。
• 每层开始时辅助变量必须重置。凡是把状态存在循环外的变量里，都要问一句「换行时它该不该清零」，这类残留错误在样例小的时候往往看不出来。
• 面试视角：先写对二维版本，等面试官追问「空间还能不能省」再压缩，并主动说明 pre 存的是哪个格子。直接上一维却说不清变量含义，会被判断成背模板。若时间不够，口头说明「滚动数组、时间不变、空间一行」也能拿分。

解法对比

两种写法状态与转移完全相同，只在「是否保留历史行」上分岔。

二维版的价值在于每个格子都对应一个可解释的状态，纸上验算方便，而且它是唯一能还原出公共子序列本身的版本——回溯需要读任意一行。面试里先写它，面试官能直接对照你口述的状态定义。

滚动版的价值在于内存，尤其当两个串都很长、或者这段逻辑要嵌进更大的系统时。代价是变量含义随循环变化，白板上更容易写错，也失去了回溯能力。

选择标准很直接：要输出子序列内容、或者面试时间紧，就用二维；只要长度且被明确问到空间，再切滚动数组，并记得把较短的串放在内层维度。

易错点总结

• 把子序列当成子串，字符不同时直接把 dp[i][j] 置 0：text1 = "abcde"、text2 = "ace" → 求出的是最长公共子串，返回 1，正确答案是 3。
• 字符相同时写成 dp[i][j] = dp[i - 1][j - 1]，漏掉加一：text1 = "a"、text2 = "a" → 永远不计数，返回 0，正确答案是 1。
• 字符不同时写成 dp[i][j] = dp[i - 1][j - 1]（同时丢掉两个末位）：text1 = "ab"、text2 = "ba" → 把已经配好的对丢掉，返回 0，正确答案是 1。
• 取字符时忘记减一，写成 charAt(i)、charAt(j)：text1 = "a"、text2 = "a" → i = 1 时访问 charAt(1)，Java 抛 StringIndexOutOfBoundsException，Go 里是 index out of range。
• DP 表按 m x n 而不是 (m + 1) x (n + 1) 开：text1 = "a"、text2 = "a" → 在 i = 1, j = 1 写入 dp[1][1] 时越界。
• 返回 dp[m - 1][n - 1]：text1 = "ab"、text2 = "ab" → 返回 dp[1][1] = 1，漏掉了最后一个字符，正确答案是 2。
• 滚动数组每行开头忘记把 pre 重置为 0（把 pre 声明在外层循环之外）：text1 = "cba"、text2 = "abc" → 第三行第一列用到了上一行残留的 pre = 1，返回 2，正确答案是 1。
• 滚动数组里把 pre = dp[j] 放在更新 dp[j] 之后：text1 = "a"、text2 = "aa" → pre 拿到的是当前行新值，同一个 'a' 被配对两次，返回 2，正确答案是 1。
• 滚动数组内层照搬 01 背包的倒序遍历：text1 = "ab"、text2 = "ab" → dp[j - 1] 读到的是上一行的值，返回 1，正确答案是 2。
• 把答案理解成两串公共字符的个数（排序后取交集）：text1 = "ab"、text2 = "ba" → 交集大小是 2，但子序列必须保序，正确答案是 1。

相似题目

题目	难度	考察点
72. 编辑距离	中等	同一张表求最小代价，字符不同时要加一并多出「替换」这一个来源
97. 交错字符串	中等	状态值从「最大长度」变成「是否可行」，转移取或而不是取最大值
516. 最长回文子序列	中等	只有一个串，等价于它与自身反转串求本题；也可直接用区间 DP，枚举顺序变成按长度
583. 两个字符串的删除操作	中等	答案是两串长度和减去两倍本题结果，考的是把删除次数翻译成保留长度
712. 两个字符串的最小ASCII删除和	中等	每个字符的权重不再是 1 而是 ASCII 值，最大化保留权重而不是保留个数
718. 最长重复子数组	中等	要求连续，字符不同时必须归零，答案取全表最大值而不是右下角
1035. 不相交的线	中等	换成两行数字连线，剥掉几何外壳后与本题完全同构，考的是识别模型
LCR 096. 交错字符串	中等	与 97 同题，第三个串的下标由前两个之和唯一确定，状态维度反而更少