##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/943.html

# 943. Find the Shortest Superstring (Hard)

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

Related Topics:
Dynamic Programming

## Solution 1. DP

// OJ: https://leetcode.com/problems/find-the-shortest-superstring/
// Time: O(N^2 * (2^N + W))
// Space: O(N * (2^N + W))
// Ref: https://leetcode.com/problems/find-the-shortest-superstring/solution/
class Solution {
public:
string shortestSuperstring(vector<string>& A) {
int N = A.size();
vector<vector<int>> overlaps(N, vector<int>(N));
for (int i = 0; i < N ; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) continue;
int len = min(A[i].size(), A[j].size());
for (int k = len; k >= 0; --k) {
if (A[i].substr(A[i].size() - k) != (A[j].substr(0, k))) continue;
overlaps[i][j] = k;
break;
}
}
}
vector<vector<int>> dp(1 << N, vector<int>(N));
vector<vector<int>> parent(1 << N, vector<int>(N, -1));
for (int bit = 0; bit < N; ++bit) {
if (((mask >> bit) & 1) == 0) continue;
for (int i = 0; i < N; ++i) {
if (((pmask >> i) & 1) == 0) continue;
int val = dp[pmask][i] + overlaps[i][bit];
}
}
}
}
vector<int> perm(N);
vector<bool> seen(N);
int t = 0, mask = (1 << N) - 1, p = 0;
for (int j = 0; j < N; ++j) {
if (dp[(1 << N) - 1][j] > dp[(1 << N) - 1][p]) p = j;
}
while (p != -1) {
perm[t++] = p;
seen[p] = true;
p = p2;
}
reverse(perm.begin(), perm.begin() + t);
for (int i = 0; i < N; ++i) {
if (!seen[i]) perm[t++] = i;
}
string ans = A[perm[0]];
for (int i = 1; i < N; ++i) {
int overlap = overlaps[perm[i - 1]][perm[i]];
ans += A[perm[i]].substr(overlap);
}
return ans;
}
};

• class Solution {
public String shortestSuperstring(String[] A) {
int length = A.length;
int[][] overlaps = new int[length][length];
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (i != j) {
int strLength = Math.min(A[i].length(), A[j].length());
for (int k = strLength; k >= 0; k--) {
if (A[i].endsWith(A[j].substring(0, k))) {
overlaps[i][j] = k;
break;
}
}
}
}
}
int states = 1 << length;
int[][] dp = new int[states][length];
int[][] parents = new int[states][length];
for (int i = 0; i < length; i++) {
if (((mask >> i) & 1) > 0) {
continue;
for (int j = 0; j < length; j++) {
if (((prevMask >> j) & 1) > 0) {
int value = dp[prevMask][j] + overlaps[j][i];
}
}
}
}
}
}
int[] permutation = new int[length];
boolean[] visited = new boolean[length];
int permIndex = 0;
int mask = states - 1;
int strIndex = 0;
for (int i = 0; i < length; i++) {
if (dp[states - 1][i] > dp[states - 1][strIndex])
strIndex = i;
}
while (strIndex != -1) {
permutation[permIndex++] = strIndex;
visited[strIndex] = true;
strIndex = parentIndex;
}
for (int i = permIndex / 2 - 1; i >= 0; i--) {
int temp = permutation[i];
permutation[i] = permutation[permIndex - 1 - i];
permutation[permIndex - 1 - i] = temp;
}
for (int i = 0; i < length; i++) {
if (!visited[i])
permutation[permIndex++] = i;
}
StringBuffer sb = new StringBuffer(A[permutation[0]]);
for (int i = 1; i < length; i++) {
int overlap = overlaps[permutation[i - 1]][permutation[i]];
sb.append(A[permutation[i]].substring(overlap));
}
return sb.toString();
}
}

############

class Solution {
public String shortestSuperstring(String[] words) {
int n = words.length;
int[][] g = new int[n][n];
for (int i = 0; i < n; ++i) {
String a = words[i];
for (int j = 0; j < n; ++j) {
String b = words[j];
if (i != j) {
for (int k = Math.min(a.length(), b.length()); k > 0; --k) {
if (a.substring(a.length() - k).equals(b.substring(0, k))) {
g[i][j] = k;
break;
}
}
}
}
}
int[][] dp = new int[1 << n][n];
int[][] p = new int[1 << n][n];
for (int i = 0; i < 1 << n; ++i) {
Arrays.fill(p[i], -1);
for (int j = 0; j < n; ++j) {
if (((i >> j) & 1) == 1) {
int pi = i ^ (1 << j);
for (int k = 0; k < n; ++k) {
if (((pi >> k) & 1) == 1) {
int v = dp[pi][k] + g[k][j];
if (v > dp[i][j]) {
dp[i][j] = v;
p[i][j] = k;
}
}
}
}
}
}
int j = 0;
for (int i = 0; i < n; ++i) {
if (dp[(1 << n) - 1][i] > dp[(1 << n) - 1][j]) {
j = i;
}
}
List<Integer> arr = new ArrayList<>();
for (int i = (1 << n) - 1; p[i][j] != -1;) {
int k = i;
i ^= (1 << j);
j = p[k][j];
}
Set<Integer> vis = new HashSet<>(arr);
for (int i = 0; i < n; ++i) {
if (!vis.contains(i)) {
}
}
Collections.reverse(arr);
StringBuilder ans = new StringBuilder(words[arr.get(0)]);
for (int i = 1; i < n; ++i) {
int k = g[arr.get(i - 1)][arr.get(i)];
ans.append(words[arr.get(i)].substring(k));
}
return ans.toString();
}
}

• // OJ: https://leetcode.com/problems/find-the-shortest-superstring/
// Time: O(2^N * N * W)
// Space: O(2^N * N * W)
class Solution {
public:
string shortestSuperstring(vector<string>& A) {
string dp[1 << 12] = {};
int overlap[12][12] = {}, last[1 << 12] = {}, N = A.size();
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) continue;
int len = min(A[i].size(), A[j].size()) - 1;
while (len >= 1 && A[i].substr(A[i].size() - len) != A[j].substr(0, len)) --len;
overlap[i][j] = len;
}
}
for (int i = 0; i < N; ++i) {
if (mask >> i & 1) continue;
auto s = dp[mask] + A[i].substr(len);
if (dp[next].empty() || s.size() < dp[next].size()) {
dp[next] = s;
last[next] = i;
}
}
}
return dp[(1 << N) - 1];
}
};

• 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)

############

# 943. Find the Shortest Superstring
# https://leetcode.com/problems/find-the-shortest-superstring/

class Solution:
def shortestSuperstring(self, words: List[str]) -> str:

def distance(s1, s2):
for i in range(1, len(s1)):
if s2.startswith(s1[i:]):
return len(s1) - i + 1

return 1

n = len(words)
weights = [[0] * n for _ in range(n)]
dp = [[0] * n for _ in range(1 << n)]
queue = deque([(0, i, 1 << i, [i]) for i in range(n)])
full_mask = (1 << n) - 1
maxWeight, maxPath = -1, []

for i in range(n):
for j in range(i, n):
weights[i][j] = distance(words[i], words[j])
weights[j][i] = distance(words[j], words[i])

while queue:
w, node, mask, path = queue.popleft()

continue

maxWeight = w
maxPath = path
continue

for nei in range(n):
if mask & (1 << nei) > 0: continue

if new > old:
queue.append((new, nei, new_mask, path + [nei]))

res = words[maxPath[0]]

for i in range(1, n):
prev, curr = maxPath[i - 1], maxPath[i]
overlap = weights[prev][curr] - 1
res += words[curr][overlap:]

return res


• func shortestSuperstring(words []string) string {
n := len(words)
g := make([][]int, n)
for i, a := range words {
g[i] = make([]int, n)
for j, b := range words {
if i != j {
for k := min(len(a), len(b)); k > 0; k-- {
if a[len(a)-k:] == b[:k] {
g[i][j] = k
break
}
}
}
}
}
dp := make([][]int, 1<<n)
p := make([][]int, 1<<n)
for i := 0; i < 1<<n; i++ {
dp[i] = make([]int, n)
p[i] = make([]int, n)
for j := 0; j < n; j++ {
p[i][j] = -1
if ((i >> j) & 1) == 1 {
pi := i ^ (1 << j)
for k := 0; k < n; k++ {
if ((pi >> k) & 1) == 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 := 0; i < n; i++ {
if dp[(1<<n)-1][i] > dp[(1<<n)-1][j] {
j = i
}
}
arr := []int{j}
vis := make([]bool, n)
vis[j] = true
for i := (1 << n) - 1; p[i][j] != -1; {
k := i
i ^= (1 << j)
j = p[k][j]
arr = append(arr, j)
vis[j] = true
}
for i := 0; i < n; i++ {
if !vis[i] {
arr = append(arr, i)
}
}
ans := &strings.Builder{}
ans.WriteString(words[arr[n-1]])
for i := n - 2; i >= 0; i-- {
k := g[arr[i+1]][arr[i]]
ans.WriteString(words[arr[i]][k:])
}
return ans.String()
}

func min(a, b int) int {
if a < b {
return a
}
return b
}