【面试高频题】难度 3/5，求 LCS 具体方案变形题
【面试高频题】难度 3/5，求 LCS 具体方案变形题
题目描述
这是 LeetCode 上的「1092. 最短公共超序列」，难度为「困难」。
Tag : 「序列 DP」、「LCS」、「最长公共子序列」、「动态规划」、「构造」、「双指针」
给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。
（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）
示例：
输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。
提示：
str1和str2都由小写英文字母组成。
LCS 求具体方案 + 构造
为了方便，我们令 str1 为 s1，str2 为 s2，并将两者长度记为 n 和 m。
容易想到最终的方案必然是由三部分组成：两字符串的公共子序列（且必然是最长公共子序列）+ 两者特有的字符部分。
基于此，我们可以先使用对两者求 LCS，并在求具体方案时遵循：属于最长公共子序列的字符只添加一次，而特有于 s1 或 s2 的字符则独自添加一次。
求解 LCS 部分我们定义 代表考虑 s1 的前 i 个字符、考虑 s2 的前 j 的字符，形成的最长公共子序列长度（为了方便，令下标从 1 开始）。
当有了「状态定义」之后，基本上「转移方程」就是呼之欲出：
s1[i]==s2[j]: f[i][j]=f[i-1][j-1]+1 。代表「必然使用 s1[i] 与 s2[j] 时」LCS的长度。s1[i]!=s2[j]: f[i][j]=max(f[i-1][j], f[i][j-1]) 。代表「必然不使用 s1[i]
（但可能使用s2[j] ）时」 和 「必然不使用 s2[j] （但可能使用s1[i] ）时」 LCS 的长度。
❝不了解 LCS 的同学可以看前置 🧀 : LCS 模板题 ❞
当预处理出动规数组 f 之后，我们使用「双指针」和「通用 DP 求具体方案」的做法进行构造：使用 i 变量指向 s1 的尾部（即起始有 i = n ），使用 j 变量指向 s2 的尾部（即起始有 j = m ），根据 i 和 j 当前所在位置以及 f[i][j] 从何值转移而来：
- 若
i或j其一走完（i = 0或j = 0），将剩余字符追加到答案中； - 当 f[i][j] = f[i - 1][j - 1] + 1 且 s1[i] = s2[j] 时（可简化为 s1[i] = s2[j] 判断），此时
i指向的字符和j指向的字符为相同，且为LCS中的字符，将其追加到具体方案，并让i和j同时后移； - 当 f[i][j] = f[i - 1][j] ，将
s1[i]追加到答案中，令i后移； - 当 f[i][j] = f[i][j - 1] ，将
s2[j]追加到答案中，令j后移。
当条件 3 和 4 同时满足时，由于只需要输出任一具体方案，我们任取其一即可。
最后，由于我们是从后往前进行构造，在返回时需要再进行一次翻转。
Java 代码：
class Solution {
public String shortestCommonSupersequence(String str1, String str2) {
int n = str1.length(), m = str2.length();
str1 = " " + str1; str2 = " " + str2;
char[] s1 = str1.toCharArray(), s2 = str2.toCharArray();
int[][] f = new int[n + 10][m + 10];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1] + 1;
else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
StringBuilder sb = new StringBuilder();
int i = n, j = m;
while (i > 0 || j > 0) {
if (i == 0) sb.append(s2[j--]);
else if (j == 0) sb.append(s1[i--]);
else {
if (s1[i] == s2[j]) {
sb.append(s1[i]);
i--; j--;
} else if (f[i][j] == f[i - 1][j]) {
sb.append(s1[i--]);
} else {
sb.append(s2[j--]);
}
}
}
return sb.reverse().toString();
}
}
TypeScript 代码：
function shortestCommonSupersequence(s1: string, s2: string): string {
const n = s1.length, m = s2.length
s1 = " " + s1; s2 = " " + s2
const f = new Array<Array<number>>()
for (let i = 0; i < n + 10; i++) f.push(new Array<number>(m + 10).fill(0))
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1] + 1
else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1])
}
}
let ans = ""
let i = n, j = m
while (i > 0 || j > 0) {
if (i == 0) ans += s2[j--]
else if (j == 0) ans += s1[i--]
else {
if (s1[i] == s2[j]) {
ans += s1[i]
i--; j--
} else if (f[i][j] == f[i - 1][j]) {
ans += s1[i--]
} else {
ans += s2[j--]
}
}
}
return ans.split('').reverse().join('')
};
Python 代码：
class Solution:
def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
n, m = len(s1), len(s2)
s1 = " " + s1
s2 = " " + s2
f = [[0] * (m + 10) for _ in range(n + 10)]
for i in range(1, n + 1):
for j in range(1, m + 1):
f[i][j] = f[i - 1][j - 1] + 1 if s1[i] == s2[j] else max(f[i - 1][j], f[i][j - 1])
ans = ""
i, j = n, m
while i > 0 or j > 0:
if i == 0:
ans += s2[j]
j -= 1
elif j == 0:
ans += s1[i]
i -= 1
else:
if s1[i] == s2[j]:
ans += s1[i]
i -= 1
j -= 1
elif f[i][j] == f[i - 1][j]:
ans += s1[i]
i -= 1
else:
ans += s2[j]
j -= 1
return ans[::-1]
- 时间复杂度：
LCS复杂度为 O(n \times m) ；构造答案复杂度为 O(n \times m) 。整体复杂度为O(n \times m) - 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1092 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
