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 <= 121 <= words[i].length <= 20words[i]consists of lowercase English letters.- All the strings of
wordsare 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));
//assert(addition);
#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];
strcat(s, &t[len[j] - addition[IDX(i, j)]]);
i = j;
}
free(len);
free(addition);
free(dp);
free(prev);
free(stack);
return s;
}
Input
words = ["alex","loves","leetcode"]
Output
"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
}
}
Input
words = ["alex","loves","leetcode"]
Output
"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]
Input
words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output
"gctaagttcatgcatc"