LeetCode 1143. 最长公共子序列
题目描述
题意分析
从两个字符串中分别选出一些字符，使选出的字符序列完全相同，并让长度尽量大。可以跳过字符，但必须保持它们在原字符串中的先后顺序，不要求连续。
题目只要求最长长度，不要求返回具体的公共子序列。重复字符要按各自出现的位置参与匹配，不能只统计两串共同出现了哪些字符；如果没有可匹配的字符，答案就是
0。
解法一：二维动态规划
核心思路
[!blue]
两个字符串都可以跳过字符，需要同时记录两边已经考虑到的位置。定义
dp[i][j]为text1前i个字符与text2前j个字符的最长公共子序列长度。接下来只看这两个前缀的末尾是否能够配对。如果末尾字符相同，一定存在把这两个末尾配在一起的最优方案：若公共子序列还没以该字符结尾，就能在最后追加它；若已经以该字符结尾，把最后一次匹配移到两串末尾也不会破坏前面的顺序。选定这对字符后，之前的匹配只能来自两个更短前缀，因此
dp[i][j] = dp[i - 1][j - 1] + 1。如果末尾字符不同，它们无法作为同一次匹配。任何公共子序列至少跳过其中一侧的末尾：跳过
text1末尾得到dp[i - 1][j]，跳过text2末尾得到dp[i][j - 1]。取两者较大值，就保留了所有可能中的最优长度。两边都跳过的情况也已经包含在这两个子问题中，无需再单独比较左上角。任一前缀为空时，公共子序列长度都是
0，所以第0行和第0列全为0。其余状态依赖左上、上方和左方，按行从左到右计算即可。失配时保留已有长度而不清零，正是“可以跳过字符”与“必须连续”的区别。
解题步骤
- 设两串长度为
m、n，创建(m + 1) × (n + 1)的状态表，第0行和第0列保持为0。- 外层遍历
i = 1..m，内层遍历j = 1..n，比较text1[i - 1]和text2[j - 1]。- 字符相同，令
dp[i][j] = dp[i - 1][j - 1] + 1，表示新增一对匹配。- 字符不同，令
dp[i][j] = max(dp[i - 1][j], dp[i][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)) {
// 状态对应前 i、j 个字符，末尾相同才在两个短前缀上延长一位。
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, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for i := range dp {
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] {
// 状态对应前 i、j 个字符，末尾相同才在两个短前缀上延长一位。
dp[i][j] = dp[i-1][j-1] + 1
} else {
// 末尾不同，分别舍弃一侧末尾，保留较长的公共子序列。
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[m][n]
}
复杂度分析
- 时间复杂度：$O(mn)$，每个状态只做常数次比较。
- 空间复杂度：$O(mn)$，保存二维状态；计入空前缀时表大小为 $(m+1)(n+1)$。
关键点总结
[!green]
- 状态覆盖两个前缀，而不是要求公共子序列恰好以这两个字符结尾。
- 相同末尾可以配成一对，再接到两个更短前缀的最优结果后面。
- 不同末尾至少跳过一个，取上方与左方的较大值即可覆盖全部选择。
解法二：滚动数组动态规划
核心思路
[!blue]
二维表中，当前状态只依赖上一行的同列、上一行的左邻列和当前行的左邻列。因此保留一行数组就足够，另用
diagonal保存即将被覆盖的左上角状态，递推规则完全不变。计算第
i行第j列之前，dp[j]尚未更新，表示上一行的上方值；dp[j - 1]已经更新，表示当前行的左方值；diagonal则表示上一行左上角的值。字符相同时取diagonal + 1，字符不同时取max(dp[j], dp[j - 1])。先把旧
dp[j]存入up，再覆盖本列，最后令diagonal = up。这样下一列需要的旧左上角仍然保留下来。每行从左向右计算，且行首令diagonal = 0，对应上一行与空前缀的公共子序列长度。最长公共子序列对两个字符串是对称的，可以交换输入，把较短字符串放在列方向，进一步把数组长度限制为较短长度加一。
解题步骤
- 交换字符串，使
text2是较短的一侧，创建长度为text2.length + 1的全零数组。- 逐个扩展
text1的前缀，每一行开始令diagonal = 0。- 从左到右遍历列，先保存
up = dp[j]，避免覆盖上方旧值。- 字符相同时令
dp[j] = diagonal + 1，否则保留上方旧值与左方新值中的较大者。- 令
diagonal = up后继续下一列；处理完所有行，返回数组最后一项。
代码实现
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
if (text1.length() < text2.length()) {
String temp = text1;
text1 = text2;
text2 = temp;
}
int[] dp = new int[text2.length() + 1];
for (int i = 1; i <= text1.length(); i++) {
// 每行左上起点对应空前缀，重新从零开始。
int diagonal = 0;
for (int j = 1; j <= text2.length(); j++) {
// 覆盖当前列前保存旧值，供下一列用作左上角。
int up = dp[j];
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[j] = diagonal + 1;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
// 交给下一列的是旧上方值，不是本轮计算出的新值。
diagonal = up;
}
}
return dp[text2.length()];
}
}
func longestCommonSubsequence(text1 string, text2 string) int {
if len(text1) < len(text2) {
text1, text2 = text2, text1
}
dp := make([]int, len(text2)+1)
for i := 1; i <= len(text1); i++ {
// 每行左上起点对应空前缀，重新从零开始。
diagonal := 0
for j := 1; j <= len(text2); j++ {
// 覆盖当前列前保存旧值，供下一列用作左上角。
up := dp[j]
if text1[i-1] == text2[j-1] {
dp[j] = diagonal + 1
} else if dp[j-1] > dp[j] {
dp[j] = dp[j-1]
}
// 交给下一列的是旧上方值，不是本轮计算出的新值。
diagonal = up
}
}
return dp[len(text2)]
}
复杂度分析
- 时间复杂度：$O(mn)$，
m、n为两个字符串的长度。- 空间复杂度：$O(\min(m, n))$，只保存较短字符串对应的一行状态。
关键点总结
[!green]
- 滚动数组保留的是同一套前缀状态，只减少存储，不改变匹配规则。
dp[j]是上方旧值，dp[j - 1]是左方新值，diagonal是左上角旧值。- 为保持这三种来源，必须从左向右计算，并在覆盖当前列之前保存它的旧值。
易错点总结
[!yellow]
- 状态下标表示前缀长度，访问末尾字符时要减一，否则会错位或越界。
- 字符不同时不能把状态清零，公共子序列允许跳过字符，前面已经匹配出的长度仍然有效。
- 不能把输入排序再匹配，排序会改变题目要求保留的原始顺序。
- 滚动数组中，若把更新后的
dp[j]赋给diagonal，就会错误地把当前行结果当作上一行状态。- 每行都要重新令
diagonal = 0；沿用上一行末尾的值会破坏空前缀边界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 718. 最长重复子数组 | 中等 | 原题要求连续子数组，失配后当前匹配长度归零；本题允许跳过字符。 |
| 72. 编辑距离 | 中等 | 同样按两个前缀建立二维DP，原题计算编辑代价，本题计算共同子序列长度。 |
| 583. 两个字符串的删除操作 | 中等 | 用两个前缀构成二维动态规划状态；本题求最长公共子序列长度，该题仅允许删除时可由公共子序列转换。 |
| 712. 两个字符串的最小ASCII删除和 | 中等 | 用两个前缀构成二维动态规划状态；本题求最长公共子序列长度，该题删除代价改为字符编码之和。 |
| 补充题 184. 最长公共子序列的构造 | 中等 | 都用公共子序列长度的 DP；补充题还要回溯状态还原具体序列。 |