题目描述
给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。
我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。
示例1
输入： ["alex","loves","leetcode"] 输出："alexlovesleetcode" 解释： "alex"，"loves"，"leetcode" 的所有排列都会被接受。
示例2
输入： ["catg","ctaagt","gcta","ttca","atgcatc"] 输出： "gctaagttcatgcatc"
提示
- 1 <= A.length <= 12
- 1 <= A[i].length <= 20
题解
这是每日算法系列更新以来，做过最难的一道题目了，也是第一次涉及到字符串类型的题目。如果觉得难，可以忽略今天这题。
这题意思就是，给你 n 个字符串，任意两个字符串如果拼接在一起的话，首尾可能会有重合的部分，那么就按照最长的重合部分拼接上去。要求的是 n 个字符串怎么排列，然后依次拼接，得到的最终字符串长度最短？
最暴力的方法当然就是枚举所有排列，然后把他们拼起来看长度，这样的话光是阶乘的复杂度就不可接受了。
这题就要用到状态压缩动态规划了，按照字面意思理解就是动态规划的状态是经过压缩的，那具体什么意思呢？
代码
c++
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; } };
python
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
后记
这题还是有点难度的，我还是看了答案后才自己写出来的，如果实在不会，不要勉强。
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
