class Solution {
public:
string shortestSuperstring(vector<string>& words) {
}
};
943. 最短超级串
给定一个字符串数组 words，找到以 words 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 任意一个 即可。
我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。
示例 1：
输入：words = ["alex","loves","leetcode"] 输出："alexlovesleetcode" 解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。
示例 2：
输入：words = ["catg","ctaagt","gcta","ttca","atgcatc"] 输出："gctaagttcatgcatc"
提示：
1 <= words.length <= 121 <= words[i].length <= 20words[i] 由小写英文字母组成words 中的所有字符串 互不相同原站题解
python3 解法, 执行用时: 1612 ms, 内存消耗: 17.3 MB, 提交时间: 2023-10-09 10:45:03
class Solution:
def overlap(self, a, b):
na, nb = len(a), len(b)
for i in range(min(na, nb), 0, -1):
if a[na-i:] == b[0:i]:
return i
return 0
def shortestSuperstring(self, A: List[str]) -> str:
INF = 0x3f3f3f3f
n= len(A)
M = 1<<n
o = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
o[i][j] = self.overlap(A[i], A[j])
dp = [[INF] * n for _ in range(M)]
path = [[0] * n for _ in range(M)]
for i in range(n):
dp[1<<i][i] = len(A[i])
for s in range(M):
for i in range(n):
if s^(1<<i) == 0:
continue
for j in range(n):
if i != j and ((s>>j)&1):
if dp[s][i] > dp[s^(1<<i)][j]+len(A[i])-o[j][i]:
dp[s][i] = dp[s^(1<<i)][j]+len(A[i])-o[j][i]
path[s][i] = j
last = 0
for i in range(1, n):
if dp[M-1][i] < dp[M-1][last]:
last = i
seq = [last]
s = M - 1
for _ in range(n-1):
tmp = last
last = path[s][last]
seq.append(last)
s = s^(1<<tmp)
seq = seq[::-1]
res = A[seq[0]]
for i in range(1, n):
res += A[seq[i]][o[seq[i-1]][seq[i]]:]
return res
cpp 解法, 执行用时: 72 ms, 内存消耗: 9.4 MB, 提交时间: 2023-10-09 10:44:32
class Solution {
public:
string shortestSuperstring(vector<string>& A) {
const int INF = 0x3f3f3f3f;
int n = A.size(), M = (1<<n);
int o[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
o[i][j] = overlap(A[i], A[j]);
}
}
int dp[M][n], path[M][n];
memset(dp, INF, sizeof dp);
memset(path, 0, sizeof path);
for (int i = 0; i < n; ++i) {
dp[1<<i][i] = A[i].size();
}
for (int s = 0; s < M; ++s) {
for (int i = 0; i < n; ++i) {
if ((s^(1<<i)) == 0) continue;
for (int j = 0; j < n; ++j) {
if (i != j && ((s>>j)&1)) {
if (dp[s][i] > dp[s^(1<<i)][j]+A[i].size()-o[j][i]) {
dp[s][i] = dp[s^(1<<i)][j]+A[i].size()-o[j][i];
path[s][i] = j;
}
}
}
}
}
int last = 0;
for (int i = 1; i < n; ++i) {
if (dp[M-1][i] < dp[M-1][last]) {
last = i;
}
}
vector<int> seq = {last};
int s = M - 1;
for (int i = 0; i < n-1; ++i) {
int tmp = last;
last = path[s][last];
seq.push_back(last);
s = s^(1<<tmp);
}
reverse(seq.begin(), seq.end());
string res = A[seq[0]];
for (int i = 1; i < n; ++i) {
res += A[seq[i]].substr(o[seq[i-1]][seq[i]]);
}
return res;
}
int overlap(const string& a, const string& b) {
int na = a.size(), nb = b.size();
for (int i = min(na, nb); i >= 1 ; --i) {
if (a.substr(na-i) == b.substr(0, i)) return i;
}
return 0;
}
};
java 解法, 执行用时: 26 ms, 内存消耗: 42.6 MB, 提交时间: 2023-10-09 10:42:41
class Solution {
public String shortestSuperstring(String[] A) {
int N = A.length;
// Populate overlaps
int[][] overlaps = new int[N][N];
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) if (i != j) {
int m = Math.min(A[i].length(), A[j].length());
for (int k = m; k >= 0; --k)
if (A[i].endsWith(A[j].substring(0, k))) {
overlaps[i][j] = k;
break;
}
}
// dp[mask][i] = most overlap with mask, ending with ith element
int[][] dp = new int[1<<N][N];
int[][] parent = new int[1<<N][N];
for (int mask = 0; mask < (1<<N); ++mask) {
Arrays.fill(parent[mask], -1);
for (int bit = 0; bit < N; ++bit) if (((mask >> bit) & 1) > 0) {
// Let's try to find dp[mask][bit]. Previously, we had
// a collection of items represented by pmask.
int pmask = mask ^ (1 << bit);
if (pmask == 0) continue;
for (int i = 0; i < N; ++i) if (((pmask >> i) & 1) > 0) {
// For each bit i in pmask, calculate the value
// if we ended with word i, then added word 'bit'.
int val = dp[pmask][i] + overlaps[i][bit];
if (val > dp[mask][bit]) {
dp[mask][bit] = val;
parent[mask][bit] = i;
}
}
}
}
// # Answer will have length sum(len(A[i]) for i) - max(dp[-1])
// Reconstruct answer, first as a sequence 'perm' representing
// the indices of each word from left to right.
int[] perm = new int[N];
boolean[] seen = new boolean[N];
int t = 0;
int mask = (1 << N) - 1;
// p: the last element of perm (last word written left to right)
int p = 0;
for (int j = 0; j < N; ++j)
if (dp[(1<<N) - 1][j] > dp[(1<<N) - 1][p])
p = j;
// Follow parents down backwards path that retains maximum overlap
while (p != -1) {
perm[t++] = p;
seen[p] = true;
int p2 = parent[mask][p];
mask ^= 1 << p;
p = p2;
}
// Reverse perm
for (int i = 0; i < t/2; ++i) {
int v = perm[i];
perm[i] = perm[t-1-i];
perm[t-1-i] = v;
}
// Fill in remaining words not yet added
for (int i = 0; i < N; ++i) if (!seen[i])
perm[t++] = i;
// Reconstruct final answer given perm
StringBuilder ans = new StringBuilder(A[perm[0]]);
for (int i = 1; i < N; ++i) {
int overlap = overlaps[perm[i-1]][perm[i]];
ans.append(A[perm[i]].substring(overlap));
}
return ans.toString();
}
}
python3 解法, 执行用时: 676 ms, 内存消耗: 17.2 MB, 提交时间: 2023-10-09 10:42:18
'''
设 dp(mask, i) 表示已经选出的字符串为 mask（mask 是一个长度为 A.length 的二进制数，
它的第 k 位如果为 1，则表示第 k 个字符串已经选出，否则表示第 k 个字符串没有被选出），
且最后一个选出的字符串是 A[i] 时的重复部分的最大长度。在状态转移时，
我们枚举下一个选出的字符串 j，就有 dp(mask ^ (1 << j), j) = max{overlap(A[i], A[j]) + dp(mask, i)}
当然 dp(mask, i) 只记录了重复部分的最大长度，要得到这个最大长度对应的字符串，
我们还需要记录一下每个状态从哪个状态转移得来，最后通过逆推的方式还原这个字符串。
'''
class Solution:
def shortestSuperstring(self, A: List[str]) -> str:
N = len(A)
# Populate overlaps
overlaps = [[0] * N for _ in range(N)]
for i, x in enumerate(A):
for j, y in enumerate(A):
if i != j:
for ans in range(min(len(x), len(y)), -1, -1):
if x.endswith(y[:ans]):
overlaps[i][j] = ans
break
# dp[mask][i] = most overlap with mask, ending with ith element
dp = [[0] * N for _ in range(1<<N)]
parent = [[None] * N for _ in range(1<<N)]
for mask in range(1, 1 << N):
for bit in range(N):
if (mask >> bit) & 1:
# Let's try to find dp[mask][bit]. Previously, we had
# a collection of items represented by pmask.
pmask = mask ^ (1 << bit)
if pmask == 0: continue
for i in range(N):
if (pmask >> i) & 1:
# For each bit i in pmask, calculate the value
# if we ended with word i, then added word 'bit'.
value = dp[pmask][i] + overlaps[i][bit]
if value > dp[mask][bit]:
dp[mask][bit] = value
parent[mask][bit] = i
# Answer will have length sum(len(A[i]) for i) - max(dp[-1])
# Reconstruct answer:
# Follow parents down backwards path that retains maximum overlap
perm = []
mask = (1<<N) - 1
i = max(range(N), key = dp[-1].__getitem__)
while i is not None:
perm.append(i)
mask, i = mask ^ (1<<i), parent[mask][i]
# Reverse path to get forwards direction; add all remaining words
perm = perm[::-1]
seen = [False] * N
for x in perm:
seen[x] = True
perm.extend([i for i in range(N) if not seen[i]])
# Reconstruct answer given perm = word indices in left to right order
ans = [A[perm[0]]]
for i in range(1, len(perm)):
overlap = overlaps[perm[i-1]][perm[i]]
ans.append(A[perm[i]][overlap:])
return "".join(ans)