LC 943. 最短超级串
题目描述
这是 LeetCode 上的 943. 最短超级串 ，难度为 困难。
给定一个字符串数组 words，找到以 words 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 任意一个 即可。
我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。
示例 1：1
2
3
4
5输入：words = ["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。
示例 2：1
2
3输入：words = ["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"
提示：
- $1 <= words.length <= 12$
- $1 <= words[i].length <= 20$
words[i]由小写英文字母组成words中的所有字符串互不相同
状压 DP
为了方便，将 words 记为 ws。
预处理二维数组 g 来表示字符串 ws[i] 和 ws[j] 的重叠部分的长度：若 g[i][j] = len 代表字符串 ws[i] 长度为 len 的后缀与字符串 ws[j] 长度为 len 的前缀相同。
另外用一个二进制数 status 来代表当前超级串 ans 对 ws 的使用（覆盖）情况：若 status 的第 i 位为 1 代表字符串 ws[i] 已被使用（即 ws[i] 已是 ans 的子串），若 status 的第 i 位为 0 代表 ws[i] 未被使用。
我们知道，当所有的 $g[i][j] = 0$ 时，代表所有拼接方式长度均为 $\sum_{i = 0}^{n - 1}ws[i].length$，即不能通过产生重叠部分来缩短超级串的长度。
因此，最小化超级串 ans 的长度等价于最大化重叠部分的长度。
定义 $f[s][i]$ 代表当前状态为 s 且当前最后一个使用到的字符串为 ws[i] （当前超级串 ans 的结尾部分为 ws[i]）时的最大重合长度。
最终超级串的长度为所有字符串的总长度 $\sum_{i = 0}^{n - 1}ws[i].length$ 减去最大重合长度 $\max(f[2^n - 1][i])$。
不失一般性考虑 $f[s][i]$ 可用于更新哪些状态，我们可枚举接在字符串 ws[i] 后面的字符串 ws[j] 为何值：
- 由于每个字符串只能使用一次，转移需要满足
s的第i位为 $1$，s的第j位为 $0$ 的前提条件，含义为ws[i]已被使用，而ws[j]未被使用 - 满足前提条件 $1$，代表
ws[j]可接在ws[i]后面，此时有状态转移方程：
接下来，考虑如何构建具体方案。
使用二维数组 $p[s][i]$ 记录每个状态是由哪个前驱转移而来：若有 $p[s][i] = j$，代表取得最大重叠长度过程中，字符串 ws[j] 接在 ws[i] 后面。
我们从后往前对 ans 进行构造，若 ans = ws[0] + ws[1] + ... + ws[k - 1] + ws[k]，我们是先找 ws[k]，再通过 ws[k] 找 ws[k - 1]，直到将整个 ans 构建出来。
构造过程中使用变量解释如下：
ans为具体的超级串status代表当前还有哪些字符串待拼接到，初始化为 $2^n - 1$，代表还没有任何字符串拼接到ans中idx代表当前处理到的字符串下标，初始化通过遍历所有的 $f[2^n - 1][i]$ 找到合适的 $i$ 作为idxlast代表前一个处理到字符串下标，初始化为-1
一些细节：当 last 不为初始值 -1 时，需要跳过 ws[idx] 与 ws[last] 的重复部分进行拼接。
Java 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47class Solution {
public String shortestSuperstring(String[] ws) {
int n = ws.length, mask = 1 << n;
int[][] g = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
String a = ws[i], b = ws[j];
int l1 = a.length(), l2 = b.length(), len = Math.min(l1, l2);
for (int k = len; k >= 1; k--) {
if (a.substring(l1 - k).equals(b.substring(0, k))) {
g[i][j] = k;
break;
}
}
}
}
int[][] f = new int[mask][n], p = new int[mask][n];
for (int s = 0; s < mask; s++) {
for (int i = 0; i < n; i++) {
if (((s >> i) & 1) == 0) continue;
for (int j = 0; j < n; j++) {
if (((s >> j) & 1) == 1) continue;
if (f[s | (1 << j)][j] <= f[s][i] + g[i][j]) {
f[s | (1 << j)][j] = f[s][i] + g[i][j];
p[s | (1 << j)][j] = i;
}
}
}
}
int max = f[mask - 1][0], idx = 0, last = -1, status = mask - 1;
for (int i = 1; i < n; i++) {
if (max < f[mask - 1][i]) {
max = f[mask - 1][i];
idx = i;
}
}
String ans = "";
while (status != 0) {
if (last == -1) ans = ws[idx];
else ans = ws[idx].substring(0, ws[idx].length() - g[idx][last]) + ans;
last = idx;
idx = p[status][idx];
status ^= (1 << last);
}
return ans;
}
}
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class Solution:
def shortestSuperstring(self, ws: List[str]) -> str:
n, mask = len(ws), 1 << len(ws)
g = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
a, b = ws[i], ws[j]
l1, l2 = len(a), len(b)
length = min(l1, l2)
for k in range(length, 0, -1):
if a[l1 - k:] == b[:k]:
g[i][j] = k
break
f = [[0 for _ in range(n)] for _ in range(mask)]
p = [[0 for _ in range(n)] for _ in range(mask)]
for s in range(mask):
for i in range(n):
if (s >> i) & 1 == 0:
continue
for j in range(n):
if (s >> j) & 1 == 1:
continue
if f[s | (1 << j)][j] <= f[s][i] + g[i][j]:
f[s | (1 << j)][j] = f[s][i] + g[i][j]
p[s | (1 << j)][j] = i
max_val = f[mask - 1][0]
idx, last, status = 0, -1, mask - 1
for i in range(1, n):
if max_val < f[mask - 1][i]:
max_val = f[mask - 1][i]
idx = i
ans = ""
while status != 0:
if last == -1:
ans = ws[idx]
else:
ans = ws[idx][:len(ws[idx]) - g[idx][last]] + ans
last = idx
idx = p[status][idx]
status ^= 1 << last
return ans
C++ 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48class Solution {
public:
string shortestSuperstring(vector<string>& ws) {
int n = ws.size(), mask = 1 << n;
vector<vector<int>> g(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
string a = ws[i], b = ws[j];
int l1 = a.length(), l2 = b.length(), len = min(l1, l2);
for (int k = len; k >= 1; k--) {
if (a.substr(l1 - k) == b.substr(0, k)) {
g[i][j] = k;
break;
}
}
}
}
vector<vector<int>> f(mask, vector<int>(n, 0)), p(mask, vector<int>(n, 0));
for (int s = 0; s < mask; s++) {
for (int i = 0; i < n; i++) {
if (((s >> i) & 1) == 0) continue;
for (int j = 0; j < n; j++) {
if (((s >> j) & 1) == 1) continue;
if (f[s | (1 << j)][j] <= f[s][i] + g[i][j]) {
f[s | (1 << j)][j] = f[s][i] + g[i][j];
p[s | (1 << j)][j] = i;
}
}
}
}
int max = f[mask - 1][0], idx = 0, last = -1, status = mask - 1;
for (int i = 1; i < n; i++) {
if (max < f[mask - 1][i]) {
max = f[mask - 1][i];
idx = i;
}
}
string ans = "";
while (status != 0) {
if (last == -1) ans = ws[idx];
else ans = ws[idx].substr(0, ws[idx].length() - g[idx][last]) + ans;
last = idx;
idx = p[status][idx];
status ^= (1 << last);
}
return ans;
}
};
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47function shortestSuperstring(ws: string[]): string {
const n = ws.length, mask = 1 << n;
const g = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const a = ws[i], b = ws[j];
const l1 = a.length, l2 = b.length;
const len = Math.min(l1, l2);
for (let k = len; k >= 1; k--) {
if (a.substring(l1 - k) === b.substring(0, k)) {
g[i][j] = k;
break;
}
}
}
}
const f = new Array(mask).fill(0).map(() => new Array(n).fill(0));
const p = new Array(mask).fill(0).map(() => new Array(n).fill(0));
for (let s = 0; s < mask; s++) {
for (let i = 0; i < n; i++) {
if (((s >> i) & 1) === 0) continue;
for (let j = 0; j < n; j++) {
if (((s >> j) & 1) === 1) continue;
if (f[s | (1 << j)][j] <= f[s][i] + g[i][j]) {
f[s | (1 << j)][j] = f[s][i] + g[i][j];
p[s | (1 << j)][j] = i;
}
}
}
}
let max = f[mask - 1][0], idx = 0, last = -1, status = mask - 1;
for (let i = 1; i < n; i++) {
if (max < f[mask - 1][i]) {
max = f[mask - 1][i];
idx = i;
}
}
let ans = "";
while (status != 0) {
if (last === -1) ans = ws[idx];
else ans = ws[idx].substring(0, ws[idx].length - g[idx][last]) + ans;
last = idx;
idx = p[status][idx];
status ^= (1 << last);
}
return ans;
}
- 时间复杂度：将字符串 $ws[i]$ 的最大长度记为 $C = 20$，预处理复杂度为 $O(n^2 \times C)$；状态数量为 $2^n$，
DP复杂度为 $O(2^n \times n^2)$。构造答案复杂度为 $O(n)$。整体复杂度为 $O(2^n\times n^2)$ - 空间复杂度：$O(2^n \times n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.943 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
