难度: Hard
给定一个字符串数组 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 中的所有字符串 互不相同运行时间: 341 ms
内存: 17.4 MB
class Solution:
def shortestSuperstring(self, words: List[str]) -> str:
n = len(words)
g = [[0] * n for _ in range(n)]
for i, a in enumerate(words):
for j, b in enumerate(words):
if i != j:
for k in range(min(len(a), len(b)), 0, -1):
if a[-k:] == b[:k]:
g[i][j] = k
break
dp = [[0] * n for _ in range(1 << n)]
p = [[-1] * n for _ in range(1 << n)]
for i in range(1 << n):
for j in range(n):
if (i >> j) & 1:
pi = i ^ (1 << j)
for k in range(n):
if (pi >> k) & 1:
v = dp[pi][k] + g[k][j]
if v > dp[i][j]:
dp[i][j] = v
p[i][j] = k
j = 0
for i in range(n):
if dp[-1][i] > dp[-1][j]:
j = i
arr = [j]
i = (1 << n) - 1
while p[i][j] != -1:
i, j = i ^ (1 << j), p[i][j]
arr.append(j)
arr = arr[::-1]
vis = set(arr)
arr.extend([j for j in range(n) if j not in vis])
ans = [words[arr[0]]] + [words[j][g[i][j] :] for i, j in pairwise(arr)]
return ''.join(ans)
这个题解使用了动态规划的方法来解决问题。首先，我们需要构建一个图 g，其中 g[i][j] 表示将单词 j 接在单词 i 后面时可以省略的最大字符数。然后，我们使用一个动态规划数组 dp 来记录到达每个状态的最大省略字符数。状态由一个整数表示，该整数的二进制形式的每一位表示一个单词是否已经在超级串中。我们逐步构建这个超级串，每次在当前状态下添加一个新的单词，并更新 dp 数组。最后，我们通过回溯 dp 数组来构建最终的超级串。
时间复杂度: O(n^2 * l + n^2 * 2^n)
空间复杂度: O(n^2 + n)
class Solution:
def shortestSuperstring(self, words: List[str]) -> str:
n = len(words)
g = [[0] * n for _ in range(n)]
for i, a in enumerate(words):
for j, b in enumerate(words):
if i != j:
for k in range(min(len(a), len(b)), 0, -1):
if a[-k:] == b[:k]:
g[i][j] = k
break
dp = [[0] * n for _ in range(1 << n)]
p = [[-1] * n for _ in range(1 << n)]
for i in range(1 << n):
for j in range(n):
if (i >> j) & 1:
pi = i ^ (1 << j)
for k in range(n):
if (pi >> k) & 1:
v = dp[pi][k] + g[k][j]
if v > dp[i][j]:
dp[i][j] = v
p[i][j] = k
j = 0
for i in range(n):
if dp[-1][i] > dp[-1][j]:
j = i
arr = [j]
i = (1 << n) - 1
while p[i][j] != -1:
i, j = i ^ (1 << j), p[i][j]
arr.append(j)
arr = arr[::-1]
vis = set(arr)
arr.extend([j for j in range(n) if j not in vis])
ans = [words[arr[0]]] + [words[j][g[i][j] :] for i, j in pairwise(arr)]
return ''.join(ans)
在构建图g时，我们首先遍历每一对单词i和j。对于每一对单词，我们通过比较单词i的后缀和单词j的前缀来确定可以省略的最大字符数。具体操作是从最大可能的重叠长度min(len(a), len(b))开始逐渐减小重叠长度k，直到找到最长的满足a的后k个字符完全等于b的前k个字符的情况。这样，g[i][j]就记录了单词j接在单词i后面时可以省略的最大字符数。
动态规划数组dp是用来记录在特定状态下的最大省略字符数。具体来说，dp[i][j]表示的是在状态i下，以单词j结尾的超级串可以达到的最大省略字符数。这里的状态i是一个整数，其二进制表示中的每一位对应一个单词是否已经被使用过。例如，如果i的第k位是1，则表示单词k已经被包含在当前超级串中。
这种逻辑基于构建超级串的过程，其中我们每次添加一个新单词到已存在的字符串中。在更新dp数组时，我们考虑从一个状态pi（已包含某些单词的超级串）通过添加一个新单词j来形成新状态i。为此，我们需要遍历所有可能的前一个状态pi和可能作为末尾的单词k，以确保我们考虑了所有可能的单词组合和顺序。通过这种方式，我们可以保证找到拼接单词j后可以得到的最大省略字符数，并更新dp[i][j]以记录这一值。
为了构建最终的超级串，我们从dp数组的最后一个状态（所有单词都被使用过）开始回溯。首先，我们找到使dp[(1<<n)-1][j]最大的j，此时j代表超级串的最后一个单词。然后，我们使用辅助数组p来追踪在达到每个状态i时最优解中的前一个单词k。通过这种方式，我们可以从数组p中逐步回溯出整个单词的顺序，直到回到初始状态（没有单词被使用）。回溯过程中，我们记录下这些单词的顺序，然后根据这个顺序和g数组中记录的省略字符数信息来构建最终的超级串。