title
给定一个字符串数组 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中的所有字符串 互不相同
solution
class Solution:
def shortestSuperstring(self, words: List[str]) -> str:
n = len(words)
overlap = [[0] * n for _ in range(n)]
def calcu(a, b):
l1, l2 = len(a), len(b)
l = min(l1, l2)
for i in range(l, 0, -1):
if a[l1 - i:] == b[:i]:
return i
return 0
inf = float('inf')
for i, a in enumerate(words):
for j in range(n):
if j == i:
continue
b = words[j]
overlap[i][j] = calcu(a, b)
parent = {}
dp = [[inf] * n for _ in range(1 << n)]
for mask in range(1 << n):
for i in range(n):
if mask == 0:
dp[mask][i] = 0
continue
elif mask & (mask - 1) == 0:
dp[mask][i] = len(words[i])
continue
if (1 << i) & mask:
bit = mask ^ (1 << i)
for j in range(n):
if (1 << j) & bit and j != i:
origin = dp[mask][i]
dp[mask][i] = min(dp[mask][i], dp[bit][j] + len(words[i]) - overlap[j][i])
if dp[mask][i] != origin:
parent[(mask, i)] = (bit, j)
lst = min(dp[(1 << n) - 1][i] for i in range(n))
ans = ""
def dfs(mask, i):
nonlocal ans
if (mask, i) not in parent:
ans = words[i] + ans
return
bit, j = parent[(mask, i)]
ans = words[i][overlap[j][i]:] + ans
dfs(bit, j)
for i in range(n):
if dp[(1 << n) - 1][i] == lst:
dfs((1 << n) - 1, i)
break
return ans