## Algorithm

Problem Name: 943. Find the Shortest Superstring

Given an array of strings `words`, return the smallest string that contains each string in `words` as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in `words` is a substring of another string in `words`.

Example 1:

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

Example 2:

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

Constraints:

• `1 <= words.length <= 12`
• `1 <= words[i].length <= 20`
• `words[i]` consists of lowercase English letters.
• All the strings of `words` are unique.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int tail_length(const char *a, int la, const char *b, int lb) {
int i = 0;
int max = la < lb ? la - 1 : lb - 1;    // max overlap characters
while (max && strncmp(&a[la - max], b, max)) {
max --;
}
return lb - max;
}
char * shortestSuperstring(char ** A, int ASize){
int *len, *addition, *dp, *prev, *stack;
int sz, i, j, p, k, l, sp;
int min = 0, last;

char *s, *t;

len = malloc(ASize * sizeof(int));
//assert(len);

for (i = 0; i < ASize; i ++) {
len[i] = strlen(A[i]);
}

addition = calloc(ASize * ASize, sizeof(int));
#define IDX(I, J) ((I) * ASize + (J))

for (i = 0; i < ASize; i ++) {
for (j = i + 1; j < ASize; j ++) {
// additional length of A[i] if combine it with A[j]
addition[IDX(i, j)] = tail_length(A[i], len[i], A[j], len[j]);
addition[IDX(j, i)] = tail_length(A[j], len[j], A[i], len[i]);
}
}

sz = (1 << ASize);  // each bit of (sz - 1) identifies one string in A

dp = calloc(sz * ASize, sizeof(int));
prev = calloc(sz * ASize, sizeof(int));
//assert(dp && path);
#define IDX2(I, J) ((I) * (ASize) + (J))

for (i = 0; i < ASize; i ++) {
dp[IDX2(1 << i, i)] = len[i];   // when there is no parent, the length is itself.
}

for (i = 1; i < sz; i ++) {         // current combination of strings being selected
for (j = 0; j < ASize; j ++) {  // the one in the ends in above combination
if (!(i & (1 << j))) continue;  // if A[j] is not in the above combination
p = i & ~(1 << j);          // new combination excluding current string A[j]
for (k = 0; k < ASize; k ++) {
if (dp[IDX2(p, k)]) {   // if the length of the new combination with A[k] in the end is known
l = dp[IDX2(p, k)] + addition[IDX(k, j)];
if (dp[IDX2(i, j)] == 0 ||
dp[IDX2(i, j)] > l) {
dp[IDX2(i, j)] = l;
prev[IDX2(i, j)] = k;   // A[j] is after A[k]
}
}
}
if (i == sz - 1 &&              // all strings are selected
(l = dp[IDX2(i, j)]) &&
(min == 0 || min > l)) {    // and a minimal length is found
min = l;
last = j;                   // record the ending string A[j]
}
}
}

stack = malloc(ASize * sizeof(int));
//assert(stack);
sp = 0;

p = sz - 1;             // all are selected
while (p > 0) {
stack[sp ++] = last;
l = p;
p &= ~(1 << last);
last = prev[IDX2(l, last)];
}

s = malloc((min + 1) * sizeof(char));
//assert(s);

i = stack[ -- sp];
strcpy(s, A[i]);

while (sp) {
j = stack[ -- sp];
t = A[j];
i = j;
}

free(len);
free(dp);
free(prev);
free(stack);

return s;
}
``````
Copy The Code &

Input

cmd
words = ["alex","loves","leetcode"]

Output

cmd
"alexlovesleetcode"

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const shortestSuperstring = function(arr) {
while (arr.length > 1) {
let maxCommonLength = 0
let maxCommonString = arr[0] + arr[1]
let maxCommonWords = [arr[0], arr[1]]
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
const { commonLength, commonString } = checkCommonPair(arr[i], arr[j])
if (commonString && commonLength >= maxCommonLength) {
maxCommonLength = commonLength
maxCommonString = commonString
maxCommonWords = [arr[i], arr[j]]
}
}
}
arr = arr.filter(
word => word !== maxCommonWords[0] && word !== maxCommonWords[1]
)
arr.unshift(maxCommonString)
}
return arr[0]
}

const checkCommonPair = function(s1, s2) {
let maxCommonLength = 0
let commonString = ''
if (s1.length > s2.length) s1, (s2 = s2), s1
for (let stringLength = 1; stringLength < s1.length; stringLength++) {
const s1Suffix = s1.substring(s1.length - stringLength)
const s2Prefix = s2.substring(0, stringLength)
if (s1Suffix === s2Prefix && stringLength > maxCommonLength) {
maxCommonLength = stringLength
commonString = s1 + s2.substring(stringLength)
}
}
for (let stringLength = 1; stringLength < s1.length; stringLength++) {
const s1Prefix = s1.substring(0, stringLength)
const s2Suffix = s2.substring(s2.length - stringLength)
if (s1Prefix === s2Suffix && stringLength > maxCommonLength) {
if (stringLength > maxCommonLength) {
maxCommonLength = stringLength
commonString = s2 + s1.substring(stringLength)
}
}
}

return {
commonLength: maxCommonLength,
commonString
}
}
``````
Copy The Code &

Input

cmd
words = ["alex","loves","leetcode"]

Output

cmd
"alexlovesleetcode"

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def shortestSuperstring(self, A):
def merge(a, b):
for i in range(len(b), 0, -1):
if a.endswith(b[:i]):
return i
return 0
def dfs(sup, s, st):
if len(sup + "".join(st)) < len(res[0]):
res[0] = sup + "".join(st)
if st and any(new in st for new in merged[s][1:]):
for new in merged[s][1:]:
if new in st:
dfs(sup + new[merged[s][0]:], new, st - {new})
else:
for nex in st:
for new in merged[nex][1:]:
if new in st:
dfs(sup + nex + new[merged[nex][0]:], new, st - {nex, new})
merged = {}
for a, b in itertools.combinations(A, 2):
for a, b in ((a, b), (b, a)):
s = merge(a, b)
if a not in merged or s > merged[a][0]:
merged[a] = [s, b]
elif s == merged[a][0]:
merged[a].append(b)
res, st = ["".join(A)], set(A)
for a in A:
dfs(a, a, st - {a})
return res[0]
``````
Copy The Code &

Input

cmd
words = ["catg","ctaagt","gcta","ttca","atgcatc"]

Output

cmd
"gctaagttcatgcatc"