# 943. Find the Shortest Superstring

Given an array A of strings, find any smallest string that contains each string in `A` as a substring.

We may assume that no string in `A` is substring of another string in `A`.

Example 1:

``````Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.
``````

Example 2:

``````Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"
``````

Note:

1. `1 <= A.length <= 12`
2. `1 <= A[i].length <= 20`

``````class Solution {
public:
string shortestSuperstring(vector<string>& A) {
int n = A.size(), mn = INT_MAX;
vector<int> order(n), best_order;
vector<vector<int>> overlap(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
for (int k = min(A[i].size(), A[j].size()); k > 0; --k) {
if (A[i].substr(A[i].size() - k) == A[j].substr(0, k)) {
overlap[i][j] = k;
break;
}
}
}
}
helper(A, overlap, 0, 0, 0, mn, order, best_order);
string res = A[best_order[0]];
for (int k = 1; k < n; ++k) {
int i = best_order[k - 1], j = best_order[k];
res += A[j].substr(overlap[i][j]);
}
return res;
}
void helper(vector<string>& A, vector<vector<int>>& overlap, int cur, int used, int curLen, int& mn, vector<int>& order, vector<int>& best_order) {
if (curLen >= mn) return;
if (cur == A.size()) {
mn = curLen;
best_order = order;
return;
}
for (int i = 0; i < A.size(); ++i) {
if (used & (1 << i)) continue;
order[cur] = i;
int nextLen = (cur == 0) ? A[i].size() : curLen + A[i].size() - overlap[order[cur - 1]][i];
helper(A, overlap, cur + 1, used | (1 << i), nextLen, mn, order, best_order);
}
}
};
``````

``````class Solution {
public:
string shortestSuperstring(vector<string>& A) {
int n = A.size();
vector<vector<string>> dp(1 << n, vector<string>(n));
vector<vector<int>> overlap(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
for (int k = min(A[i].size(), A[j].size()); k > 0; --k) {
if (A[i].substr(A[i].size() - k) == A[j].substr(0, k)) {
overlap[i][j] = k;
break;
}
}
}
}
for (int i = 0; i < n; ++i) dp[1 << i][i] += A[i];
for (int j = 0; j < n; ++j) {
if ((mask & (1 << j)) == 0) continue;
for (int i = 0; i < n; ++i) {
if (i == j || (mask & (1 << i)) == 0) continue;
string t = dp[mask ^ (1 << j)][i] + A[j].substr(overlap[i][j]);
}
}
}
}
int last = (1 << n) - 1;
string res = dp[last][0];
for (int i = 1; i < n; ++i) {
if (dp[last][i].size() < res.size()) {
res = dp[last][i];
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/943

https://leetcode.com/problems/find-the-shortest-superstring/

https://leetcode.com/problems/find-the-shortest-superstring/discuss/194932/Travelling-Salesman-Problem

https://leetcode.com/problems/find-the-shortest-superstring/discuss/195290/C%2B%2B-solution-in-less-than-30-lines

https://leetcode.com/problems/find-the-shortest-superstring/discuss/199029/Rewrite-the-official-solution-in-C%2B%2B

https://leetcode.com/problems/find-the-shortest-superstring/discuss/198920/Shortest-Hamiltonian-Path-in-weighted-digraph-(with-instructional-explanation)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation