题目形容
这是 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"。最终咱们给出的答案是满足上述属性的最短字符串。提醒：
- $1 <= str1.length, str2.length <= 1000$
str1和str2都由小写英文字母组成。
LCS 求具体计划 + 结构
为了不便，咱们令 str1 为 s1，str2 为 s2，并将两者长度记为 $n$ 和 $m$。
容易想到最终的计划必然是由三局部组成：两字符串的公共子序列（且必然是最长公共子序列）+ 两者特有的字符局部。
基于此，咱们能够先应用对两者求 LCS，并在求具体计划时遵循：属于最长公共子序列的字符只增加一次，而特有于 s1 或 s2 的字符则单独增加一次。
求解 LCS 局部咱们定义 $f[i][j]$ 代表思考 $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)$ - 空间复杂度：$O(n \times m)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1092 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布