LeetCode 1092. 最短公共超序列
题目描述
题意分析
构造一个长度最短的字符串，使
str1和str2都能作为它的子序列出现。允许在两个输入的字符之间穿插其他字符，但每个输入串内部的字符顺序都必须保留，不能只按字母数量合并。要求返回构造出的字符串，而不只是最短长度。若存在多个同样短的答案，返回任意一个即可，不需要追求字典序最小。相同字符可以被两个输入共同使用，从而缩短结果。
解法：LCS 辅助重建
核心思路
[!blue]
先把两个串完整拼接，长度为
m + n。要让结果更短，就需要让两个输入共用某些字符位置。共用的位置在两个串中都必须保持相同先后顺序，因此它们一定构成公共子序列，最多只能共用最长公共子序列的长度L。所以任何结果都至少有m + n - L个字符。用后缀 LCS 表记录可以共用多少字符：
dp[i][j]表示str1[i..)与str2[j..)的最长公共子序列长度。当前字符相等时可共同使用，状态为1 + dp[i + 1][j + 1]；不等时至少要先处理其中一侧，取dp[i + 1][j]和dp[i][j + 1]的较大值。空后缀的 LCS 为零，依赖更大的下标，所以倒序填表。重建从两个起点开始。如果当前字符相同，就输出一次并同时推进两边，共享这个位置。如果不同，就把其中一个当前字符单独输出，再推进这一侧；选择哪一侧，取决于消耗它之后能留下多少公共字符，选择对应后缀 LCS 更大的方向即可，平局时任选。
这里的“消耗”不是删除输入字符：这个字符已经写入结果，只是不与另一侧共享。每步都输出某个输入当前最前面的未处理字符，因此两串的相对顺序始终保留。沿表中最优转移恰好共用
L次，最后长度达到m + n - L，也就达到了前面的最短下界。一侧耗尽后，另一侧没有可共享的对象，剩余字符必须全部原序追加。保留完整 DP 表是为了在重建时查询后续最优方向，仅有一个最终 LCS 长度不足以完成这一步。
解题步骤
- 创建
(m + 1) × (n + 1)的后缀 LCS 表，末行与末列保持零。- 从后向前比较两串字符，按相等取右下对角加一、不等取两个后缀最大值的规则填表。
- 从
i = 0、j = 0开始构造：相等时输出一个字符并同时推进。- 不等时比较
dp[i + 1][j]与dp[i][j + 1]，输出保留更多公共字符的那一侧当前字符，并只推进这一侧。- 一侧用完后追加另一侧剩余后缀，返回结果。
代码实现
class Solution {
public String shortestCommonSupersequence(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] dp = new int[m + 1][n + 1];
// 后缀依赖更大的下标，按逆序填表。
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (str1.charAt(i) == str2.charAt(j)) {
dp[i][j] = dp[i + 1][j + 1] + 1;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
StringBuilder answer = new StringBuilder();
int i = 0;
int j = 0;
while (i < m && j < n) {
if (str1.charAt(i) == str2.charAt(j)) {
answer.append(str1.charAt(i));
i++;
j++;
} else if (dp[i + 1][j] >= dp[i][j + 1]) {
// 消耗这一侧后保留更多公共字符；相等时任选。
answer.append(str1.charAt(i));
i++;
} else {
answer.append(str2.charAt(j));
j++;
}
}
// 其中一串已耗尽，把剩余字符全部保留。
answer.append(str1.substring(i));
answer.append(str2.substring(j));
return answer.toString();
}
}
func shortestCommonSupersequence(str1 string, str2 string) string {
m, n := len(str1), len(str2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 后缀依赖更大的下标，按逆序填表。
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if str1[i] == str2[j] {
dp[i][j] = dp[i+1][j+1] + 1
} else if dp[i+1][j] >= dp[i][j+1] {
// 消耗这一侧后保留更多公共字符；相等时任选。
dp[i][j] = dp[i+1][j]
} else {
dp[i][j] = dp[i][j+1]
}
}
}
answer := make([]byte, 0, m+n)
i, j := 0, 0
for i < m && j < n {
if str1[i] == str2[j] {
answer = append(answer, str1[i])
i++
j++
} else if dp[i+1][j] >= dp[i][j+1] {
// 消耗这一侧后保留更多公共字符；相等时任选。
answer = append(answer, str1[i])
i++
} else {
answer = append(answer, str2[j])
j++
}
}
// 其中一串已耗尽，把剩余字符全部保留。
answer = append(answer, str1[i:]...)
answer = append(answer, str2[j:]...)
return string(answer)
}
复杂度分析
- 时间复杂度：
O(mn + m + n)。填表处理mn个状态，构造过程每步至少推进一个输入下标，总长度不超过m + n。- 空间复杂度：
O(mn + m + n)，包括完整 DP 表和用于构造结果的字符缓冲区。
关键点总结
[!green]
- 共用字符必须形成公共子序列，给出最短长度下界
m + n - LCS。- LCS 表决定下一步怎样保留最多共享机会，构造结果能达到该下界。
- 不相等时输出一侧后推进一侧，相等时两个输入共用一个输出位置。
- 本题允许任意最短答案，分支长度相同时无需额外按字典序选择。
易错点总结
[!yellow]
- 只按字符频次合并：忽略两个输入各自的先后顺序，不能保证它们是结果的子序列。
- 后缀状态正序填表：依赖项位于更大的下标，必须先完成后面的状态。
- 不等时同时推进两边：只写一个字符却消耗两个不同字符，会丢失必要内容。
- 按LCS回溯时只输出匹配字符：那得到的是公共子序列，未共享的字符也需要写入超序列。
- 遗漏尚未结束的一侧后缀：会使完整输入串无法作为结果的子序列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 一条LCS决定两串能共享哪些字符，围绕它合并未匹配字符可得到最短公共超序列。 |
| 583. 两个字符串的删除操作 | 中等 | 原题删除不同部分以保留共同子序列，本题合并两串的不同部分以同时容纳两串。 |