LeetCode 补充题 184. 最长公共子序列的构造
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 1143. 最长公共子序列
LeetCode 原题返回最长公共子序列的长度；本文构造并返回序列本身，无非空公共子序列时返回 "-1"。
:::
给定两个字符串，返回它们的最长公共子序列本身。不存在非空公共子序列时返回
"-1"。题目保证最长答案唯一；下面代码在多解时也返回其中一个最长答案。
示例 1：
输入：
a = "abcde", b = "ace"
输出："ace"
解释：a中依次选取a、c、e，与b完全一致。
示例 2：
输入：
a = "abc", b = "xyz"
输出："-1"
解释： 没有共同字符，按约定返回字符串"-1"。
提示：
0 <= a.length,b.length <= 2000
题意分析
公共子序列允许跳过字符，但两串中的相对顺序必须一致。用两个前缀的最长公共子序列长度描述子问题，再沿取得最优值的选择回溯，才能恢复具体答案。
解法：二维 LCS 表回溯具体序列
核心思路
[!blue]
dp[i][j]表示前i个、前j个码点的 LCS 长度。末字符相同，可以接在较短前缀的 LCS 后，得到dp[i-1][j-1]+1；不相同时两者不能共同作为末项，取跳过任意一侧末字符的较大值。空前缀状态为 0。从右下角回溯，字符相同就记录它并同时退一步；不同时走向上方或左方中保留最优长度的格子。相等时固定选上方即可，因为只需一条最优结果；题面又保证最长答案唯一。
回溯按从后往前收集，最后反转得到原顺序。二维表保留了回溯所需信息，不能只保留最终一行就直接执行同样恢复；最终长度为 0 时按题面返回字符串
-1。
解题步骤
- 建立二维前缀长度表。
- 从右下角沿保持最优长度的方向回溯，相等字符加入缓冲区。
- 反转缓冲区；没有非空公共序列时返回-1。
代码实现
class Solution {
public String lcs(String a, String b) {
int[] x = a.codePoints().toArray();
int[] y = b.codePoints().toArray();
int m = x.length;
int n = y.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] =
x[i - 1] == y[j - 1]
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
if (dp[m][n] == 0) {
return "-1";
}
StringBuilder result = new StringBuilder();
while (m > 0 && n > 0) {
if (x[m - 1] == y[n - 1]) {
result.appendCodePoint(x[--m]);
n--;
} else if (dp[m - 1][n] >= dp[m][n - 1]) {
m--;
} else {
n--;
}
}
return result.reverse().toString();
}
}
func lcs(a, b string) string {
x, y := []rune(a), []rune(b)
m, n := len(x), len(y)
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 x[i-1] == y[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
if dp[m][n] == 0 {
return "-1"
}
result := make([]rune, 0, dp[m][n])
for m > 0 && n > 0 {
if x[m-1] == y[n-1] {
result = append(result, x[m-1])
m--
n--
} else if dp[m-1][n] >= dp[m][n-1] {
m--
} else {
n--
}
}
for l, r := 0, len(result)-1; l < r; l, r = l+1, r-1 {
result[l], result[r] = result[r], result[l]
}
return string(result)
}
复杂度分析
- 时间复杂度：$O(mn)$。
- 空间复杂度：额外空间 $O(mn)$。
关键点总结
[!green]
收集次序是逆序，最后反转；不能使用只有最终长度的滚动表来直接回溯。
易错点总结
[!yellow]
相等时同时移动两个下标；答案需反转；空结果按原题返回 -1，不返回长度 0。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 同一长度递推，本题还需保留回溯信息并返回字符序列，不能只返回最终长度。 |
| 72. 编辑距离 | 中等 | 同样从二维最优状态表恢复一条决策路径，但编辑距离的边表示编辑操作，而非共同字符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！