LeetCode LCR 095. 最长公共子序列
题目描述
题意分析
求两个字符串最长公共子序列的长度。子序列允许跳过字符，但必须保持各自的相对顺序，因此不能只统计共有字符，也不能在失配时把此前结果清零。
同时处理两个字符串，需要分别记录已经使用的前缀长度。相同的两个前缀，无论通过什么删除过程得到，最长公共子序列长度都相同，可以合并为一个状态。
解法一：二维动态规划
核心思路
[!blue]
定义
dp[i][j]为text1前i个字符与text2前j个字符的最长公共子序列长度。下标表示前缀长度，零表示空前缀，因此第一行、第一列都为零；整串答案是dp[m][n]。比较两个前缀的末尾字符
text1[i - 1]和text2[j - 1]，分两种情况：
- 末尾相同：可以让它们配成公共子序列的最后一对，得到
dp[i - 1][j - 1] + 1。若一个最优方案只使用了其中一个末位，可以把另一串中对应的匹配移到末位，不改变前面的顺序；若两个末位都没有使用，则还可以接上这一对。因此存在配对这两个末位的最优方案，不会因直接使用它们而漏解。- 末尾不同：它们不能同时作为公共子序列的最后一个字符，至少要舍弃其中一侧的末位。分别考虑
dp[i - 1][j]和dp[i][j - 1]，取较大值。无需额外考虑同时舍弃两者，因为更短的两个前缀不会优于这两种选择。按行、列递增填表时，上方与左上方已经在上一行算好，左方已经在当前行算好。每个状态都从更短的前缀转移，且两种字符关系覆盖了全部情况，所以可以依次求出答案。
解题步骤
- 创建
(m + 1) × (n + 1)的零数组，用多出的一行一列表示空前缀。- 从
i = 1、j = 1开始填表，比较字符下标i - 1、j - 1。- 字符相同就取左上方加一；不同就取上方和左方的最大值。
- 返回
dp[m][n]。没有公共字符时所有状态保持为零，重复字符则通过不同下标按顺序参与匹配。
代码实现
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)$，每对前缀只计算一次，每次转移为常数时间。
- 空间复杂度：$O(mn)$，保存完整二维表。
关键点总结
[!green]
- 两个下标表示前缀长度，访问末尾字符时都要减一。
- 相同字符配对才增加长度；失配只是舍弃一个末位，不清空已匹配结果。
- 空前缀为零，所有转移都有统一的边界状态。
解法二：滚动数组动态规划
核心思路
[!blue]
二维转移只用到上方、左方和左上方，不需要保存更早的行。用一行
dp原地更新时，从左到右处理各列：当前dp[j]仍是上一行同列，dp[j - 1]已是本行左侧。左上方的旧值已经在上一列被覆盖，因此额外用
pre保存它。每列先用up = dp[j]留下上方旧值，再计算新状态：字符相同取pre + 1，不同取旧dp[j]与新dp[j - 1]的较大值。本列结束后令
pre = up。本列的上方，正好就是下一列所需的左上方，所以旧值可以这样逐列传递。每行开始时要把pre重置为零，对应上一行第零列的空前缀状态。内层必须从左向右推进，才能读到本行已经更新的左侧值。滚动只改变状态的保存方式，递推含义和最终答案与二维版本相同。
解题步骤
- 创建长度为
n + 1的零数组，表示二维表的第零行。- 每处理
text1的一个字符，先令pre = 0，再从左向右遍历text2。- 覆盖
dp[j]前保存up；根据字符是否相同，用左上旧值或上旧值、左新值完成转移。- 令
pre = up供下一列使用，所有行完成后返回dp[n]。
代码实现
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)$，保存一行状态和两个临时值。
关键点总结
[!green]
- 更新前的
dp[j]是上方旧值，更新后的dp[j - 1]是本行左值。pre保存左上旧值，必须先备份up，再覆盖当前格。- 每行重新令
pre = 0，不能沿用上一行末尾的值。
解法对比：
两种写法的状态与转移相同。二维版保留完整历史，便于从右下角沿转移回溯一个公共子序列；当前滚动版只保留计算长度需要的信息，用一行空间完成同样的长度计算。
易错点总结
[!yellow]
- 子序列允许跳过字符但必须保持顺序；失配时取上方、左方最大值，不清零。
- 滚动数组中的 pre 保存上一行左上角旧值，更新当前格前先备份上方。
- 每一行开始重置 pre=0，内层从左向右扫描以读取本行左侧结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 718. 最长重复子数组 | 中等 | 原题要求连续子数组，失配后当前匹配长度归零；本题允许跳过字符。 |
| 72. 编辑距离 | 中等 | 同样按两个前缀建立二维DP，原题计算编辑代价，本题计算共同子序列长度。 |