共计 3344 个字符,预计需要花费 9 分钟才能阅读完成。
题目形容
这是 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 多平台公布