Given a set of n strings arr[], find the smallest string that contains each string in the given set as substring. We may assume that no string in arr[] is substring of another string.
Examples:
Input: arr[] = {"geeks", "quiz", "for"}
Output: geeksquizfor
Input: arr[] = {"catg", "ctaagt", "gcta", "ttca", "atgcatc"}
Output: gctaagttcatgcatc
Shortest Superstring Greedy Approximate Algorithm
Shortest Superstring Problem is a NP Hard problem. A solution that always finds shortest superstring takes exponential time. Below is an Approximate Greedy algorithm.
Let arr[] be given set of strings.
1) Create an auxiliary array of strings, temp[]. Copy contents
of arr[] to temp[]
2) While temp[] contains more than one strings
a) Find the most overlapping string pair in temp[]. Let this
pair be 'a' and 'b'.
b) Replace 'a' and 'b' with the string obtained after combining
them.
3) The only string left in temp[] is the result, return it.
Two strings are overlapping if prefix of one string is same suffix of other string or vice versa. The maximum overlap mean length of the matching prefix and suffix is maximum.
Working of above Algorithm:
arr[] = {"catgc", "ctaagt", "gcta", "ttca", "atgcatc"}
Initialize:
temp[] = {"catgc", "ctaagt", "gcta", "ttca", "atgcatc"}
The most overlapping strings are "catgc" and "atgcatc"
(Suffix of length 4 of "catgc" is same as prefix of "atgcatc")
Replace two strings with "catgcatc", we get
temp[] = {"catgcatc", "ctaagt", "gcta", "ttca"}
The most overlapping strings are "ctaagt" and "gcta"
(Prefix of length 3 of "ctaagt" is same as suffix of "gcta")
Replace two strings with "gctaagt", we get
temp[] = {"catgcatc", "gctaagt", "ttca"}
The most overlapping strings are "catgcatc" and "ttca"
(Prefix of length 2 of "catgcatc" as suffix of "ttca")
Replace two strings with "ttcatgcatc", we get
temp[] = {"ttcatgcatc", "gctaagt"}
Now there are only two strings in temp[], after combing
the two in optimal way, we get tem[] = {"gctaagttcatgcatc"}
Since temp[] has only one string now, return it.
Below is the implementation of the above algorithm.
C++
#include <bits/stdc++.h>
using namespace std;
int min(int a, int b)
{
return (a < b) ? a : b;
}
int findOverlappingPair(string str1,
string str2, string &str)
{
int max = INT_MIN;
int len1 = str1.length();
int len2 = str2.length();
for (int i = 1; i <=
min(len1, len2); i++)
{
if (str1.compare(len1-i, i, str2,
0, i) == 0)
{
if (max < i)
{
max = i;
str = str1 + str2.substr(i);
}
}
}
for (int i = 1; i <=
min(len1, len2); i++)
{
if (str1.compare(0, i, str2,
len2-i, i) == 0)
{
if (max < i)
{
max = i;
str = str2 + str1.substr(i);
}
}
}
return max;
}
string findShortestSuperstring(string arr[],
int len)
{
while(len != 1)
{
int max = INT_MIN;
int l, r;
string resStr;
for (int i = 0; i < len; i++)
{
for (int j = i + 1; j < len; j++)
{
string str;
int res = findOverlappingPair(arr[i],
arr[j], str);
if (max < res)
{
max = res;
resStr.assign(str);
l = i, r = j;
}
}
}
len--;
if (max == INT_MIN)
arr[0] += arr[len];
else
{
arr[l] = resStr;
arr[r] = arr[len];
}
}
return arr[0];
}
int main()
{
string arr[] = {"catgc", "ctaagt",
"gcta", "ttca", "atgcatc"};
int len = sizeof(arr)/sizeof(arr[0]);
cout << "The Shortest Superstring is "
<< findShortestSuperstring(arr, len);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG
{
static String str;
static int min(int a, int b)
{
return (a < b) ? a : b;
}
static int findOverlappingPair(String str1,
String str2)
{
int max = Integer.MIN_VALUE;
int len1 = str1.length();
int len2 = str2.length();
for (int i = 1; i <=
min(len1, len2); i++)
{
if (str1.substring(len1 - i).compareTo(
str2.substring(0, i)) == 0)
{
if (max < i)
{
max = i;
str = str1 + str2.substring(i);
}
}
}
for (int i = 1; i <=
min(len1, len2); i++)
{
if (str1.substring(0, i).compareTo(
str2.substring(len2 - i)) == 0)
{
if (max < i)
{
max = i;
str = str2 + str1.substring(i);
}
}
}
return max;
}
static String findShortestSuperstring(
String arr[], int len)
{
while (len != 1)
{
int max = Integer.MIN_VALUE;
int l = 0, r = 0;
String resStr = "";
for (int i = 0; i < len; i++)
{
for (int j = i + 1; j < len; j++)
{
int res = findOverlappingPair
(arr[i], arr[j]);
if (max < res)
{
max = res;
resStr = str;
l = i;
r = j;
}
}
}
len--;
if (max == Integer.MIN_VALUE)
arr[0] += arr[len];
else
{
arr[l] = resStr;
arr[r] = arr[len];
}
}
return arr[0];
}
public static void main(String[] args)
{
String[] arr = { "catgc", "ctaagt",
"gcta", "ttca", "atgcatc" };
int len = arr.length;
System.out.println("The Shortest Superstring is " +
findShortestSuperstring(arr, len));
}
}
|
Python
import sys
def minimum(a, b):
return a if a < b else b
def findOverlappingPair(str1, str2):
max_len = -sys.maxsize
len1 = len(str1)
len2 = len(str2)
str_ = ""
for i in range(1, minimum(len1, len2)+1):
if str1[len1-i:] == str2[:i]:
if max_len < i:
max_len = i
str_ = str1 + str2[i:]
for i in range(1, minimum(len1, len2)+1):
if str1[:i] == str2[len2-i:]:
if max_len < i:
max_len = i
str_ = str2 + str1[i:]
return max_len, str_
def findShortestSuperstring(arr, n):
while n != 1:
max_len = -sys.maxsize
l, r = 0, 0
res_str = ""
for i in range(n):
for j in range(i+1, n):
str_ = ""
res, str_ = findOverlappingPair(arr[i], arr[j])
if max_len < res:
max_len = res
res_str = str_
l, r = i, j
n -= 1
if max_len == -sys.maxsize:
arr[0] += arr[n]
else:
arr[l] = res_str
arr[r] = arr[n]
return arr[0]
if __name__ == "__main__":
arr = ["catgc", "ctaagt", "gcta", "ttca", "atgcatc"]
n = len(arr)
print("The Shortest Superstring is", findShortestSuperstring(arr, n))
|
C#
using System;
class GFG
{
static String str;
static int min(int a, int b)
{
return (a < b) ? a : b;
}
static int findOverlappingPair(String str1,
String str2)
{
int max = Int32.MinValue;
int len1 = str1.Length;
int len2 = str2.Length;
for (int i = 1; i <=
min(len1, len2); i++)
{
if (str1.Substring(len1 - i).CompareTo(
str2.Substring(0, i)) == 0)
{
if (max < i)
{
max = i;
str = str1 + str2.Substring(i);
}
}
}
for (int i = 1; i <=
min(len1, len2); i++)
{
if (str1.Substring(0, i).CompareTo(
str2.Substring(len2 - i)) == 0)
{
if (max < i)
{
max = i;
str = str2 + str1.Substring(i);
}
}
}
return max;
}
static String findShortestSuperstring(String []arr, int len)
{
while (len != 1)
{
int max = Int32.MinValue;
int l = 0, r = 0;
String resStr = "";
for (int i = 0; i < len; i++)
{
for (int j = i + 1; j < len; j++)
{
int res = findOverlappingPair
(arr[i], arr[j]);
if (max < res)
{
max = res;
resStr = str;
l = i;
r = j;
}
}
}
len--;
if (max == Int32.MinValue)
arr[0] += arr[len];
else
{
arr[l] = resStr;
arr[r] = arr[len];
}
}
return arr[0];
}
public static void Main(String[] args)
{
String[] arr = { "catgc", "ctaagt",
"gcta", "ttca", "atgcatc" };
int len = arr.Length;
Console.Write("The Shortest Superstring is " +
findShortestSuperstring(arr, len));
}
}
|
Javascript
function min(a, b) {
return (a < b) ? a : b;
}
function findOverlappingPair(str1, str2) {
let max = Number.MIN_SAFE_INTEGER;
let len1 = str1.length;
let len2 = str2.length;
let str = "";
for (let i = 1; i <= min(len1, len2); i++) {
if (str1.substring(len1 - i) === str2.substring(0, i)) {
if (max < i) {
max = i;
str = str1 + str2.substring(i);
}
}
}
for (let i = 1; i <= min(len1, len2); i++) {
if (str1.substring(0, i) === str2.substring(len2 - i)) {
if (max < i) {
max = i;
str = str2 + str1.substring(i);
}
}
}
return { max: max, str: str };
}
function findShortestSuperstring(arr) {
let len = arr.length;
while (len !== 1) {
let max = Number.MIN_SAFE_INTEGER;
let l = 0, r = 0;
let resStr = "";
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
let { max: res, str } = findOverlappingPair(arr[i], arr[j]);
if (max < res) {
max = res;
resStr = str;
l = i;
r = j;
}
}
}
len--;
if (max === Number.MIN_SAFE_INTEGER) {
arr[0] += arr[len];
} else {
arr[l] = resStr;
arr[r] = arr[len];
}
}
return arr[0];
}
let arr = ["catgc", "ctaagt", "gcta", "ttca", "atgcatc"];
console.log("The Shortest Superstring is " + findShortestSuperstring(arr));
|
Output
The Shortest Superstring is gctaagttcatgcatc
The time complexity of this algorithm is O(n^3 * m), where n is the number of strings in the input array and m is the maximum length of any string in the array. This is because the main loop runs n-1 times and the findOverlappingPair function takes O(m) time, and it is called n^2 times.
The space complexity is O(n * m), which is the space required to store the input array and the result string.
Performance of above algorithm:
The above Greedy Algorithm is proved to be 4 approximate (i.e., length of the superstring generated by this algorithm is never beyond 4 times the shortest possible superstring). This algorithm is conjectured to 2 approximate (nobody has found case where it generates more than twice the worst). Conjectured worst case example is {abk, bkc, bk+1}. For example {“abb”, “bbc”, “bbb”}, the above algorithm may generate “abbcbbb” (if “abb” and “bbc” are picked as first pair), but the actual shortest superstring is “abbbc”. Here ratio is 7/5, but for large k, ration approaches 2.
Another Approach:
By “greedy approach” I mean: each time we merge the two strings with a maximum length of overlap, remove them from the string array, and put the merged string into the string array.
Then the problem becomes to: find the shortest path in this graph which visits every node exactly once. This is a Travelling Salesman Problem.
Apply Travelling Salesman Problem DP solution. Remember to record the path.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int calcOverlap(string a, string b) {
for (int i = 1; i < a.length(); i++) {
if (b.find(a.substr(i)) == 0) {
return b.length() - a.length() + i;
}
}
return b.length();
}
string shortestSuperstring(vector<string> A) {
int n = A.size();
vector<vector<int>> graph(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = calcOverlap(A[i], A[j]);
graph[j][i] = calcOverlap(A[j], A[i]);
}
}
vector<vector<int>> dp(1 << n, vector<int>(n));
vector<vector<int>> path(1 << n, vector<int>(n));
int last = -1, minVal = INT_MAX;
for (int i = 1; i < (1 << n); i++) {
fill(dp[i].begin(), dp[i].end(), INT_MAX);
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) > 0) {
int prev = i - (1 << j);
if (prev == 0) {
dp[i][j] = A[j].length();
} else {
for (int k = 0; k < n; k++) {
if (dp[prev][k] < INT_MAX && dp[prev][k] + graph[k][j] < dp[i][j]) {
dp[i][j] = dp[prev][k] + graph[k][j];
path[i][j] = k;
}
}
}
}
if (i == (1 << n) - 1 && dp[i][j] < minVal) {
minVal = dp[i][j];
last = j;
}
}
}
string res;
int cur = (1 << n) - 1;
stack<int> s;
while (cur > 0) {
s.push(last);
int temp = cur;
cur -= (1 << last);
last = path[temp][last];
}
int i = s.top();
s.pop();
res += A[i];
while (!s.empty()) {
int j = s.top();
s.pop();
res += A[j].substr(A[j].length() - graph[i][j]);
i = j;
}
return res;
}
int main() {
vector<string> arr{"catgc", "ctaagt", "gcta", "ttca", "atgcatc"};
cout << "The Shortest Superstring is " << shortestSuperstring(arr) << endl;
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class Solution
{
public static String shortestSuperstring(
String[] A)
{
int n = A.length;
int[][] graph = new int[n][n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
graph[i][j] = calc(A[i], A[j]);
graph[j][i] = calc(A[j], A[i]);
}
}
int[][] dp = new int[1 << n][n];
int[][] path = new int[1 << n][n];
int last = -1, min = Integer.MAX_VALUE;
for (int i = 1; i < (1 << n); i++)
{
Arrays.fill(dp[i], Integer.MAX_VALUE);
for (int j = 0; j < n; j++)
{
if ((i & (1 << j)) > 0)
{
int prev = i - (1 << j);
if (prev == 0)
{
dp[i][j] = A[j].length();
}
else
{
for (int k = 0; k < n; k++)
{
if (dp[prev][k] < Integer.MAX_VALUE &&
dp[prev][k] + graph[k][j] < dp[i][j])
{
dp[i][j] = dp[prev][k] + graph[k][j];
path[i][j] = k;
}
}
}
}
if (i == (1 << n) - 1 && dp[i][j] < min)
{
min = dp[i][j];
last = j;
}
}
}
StringBuilder sb = new StringBuilder();
int cur = (1 << n) - 1;
Stack<Integer> stack = new Stack<>();
while (cur > 0)
{
stack.push(last);
int temp = cur;
cur -= (1 << last);
last = path[temp][last];
}
int i = stack.pop();
sb.append(A[i]);
while (!stack.isEmpty())
{
int j = stack.pop();
sb.append(A[j].substring(A[j].length() -
graph[i][j]));
i = j;
}
return sb.toString();
}
public static int calc(String a, String b)
{
for (int i = 1; i < a.length(); i++)
{
if (b.startsWith(a.substring(i)))
{
return b.length() - a.length() + i;
}
}
return b.length();
}
public static void main(String[] args)
{
String[] arr = { "catgc", "ctaagt",
"gcta", "ttca", "atgcatc" };
System.out.println("The Shortest Superstring is " +
shortestSuperstring(arr));
}
}
|
Python3
def shortestSuperstring(A):
n = len(A)
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
for j in range(n):
graph[i][j] = calc(A[i], A[j])
graph[j][i] = calc(A[j], A[i])
dp = [[0 for i in range(n)] for j in range(1 << n)]
path = [[0 for i in range(n)] for j in range(1 << n)]
last = -1
min_val = float('inf')
for i in range(1, (1 << n)):
for j in range(n):
dp[i][j] = float('inf')
for j in range(n):
if (i & (1 << j)) > 0:
prev = i - (1 << j)
if prev == 0:
dp[i][j] = len(A[j])
else:
for k in range(n):
if dp[prev][k] < float('inf') and dp[prev][k] + graph[k][j] < dp[i][j]:
dp[i][j] = dp[prev][k] + graph[k][j]
path[i][j] = k
if i == (1 << n) - 1 and dp[i][j] < min_val:
min_val = dp[i][j]
last = j
sb = ""
cur = (1 << n) - 1
stack = []
while cur > 0:
stack.append(last)
temp = cur
cur -= (1 << last)
last = path[temp][last]
i = stack.pop()
sb += A[i]
while len(stack) > 0:
j = stack.pop()
sb += A[j][len(A[j]) - graph[i][j]:]
i = j
return sb
def calc(a, b):
for i in range(1, len(a)):
if b.startswith(a[i:]):
return len(b) - len(a) + i
return len(b)
if __name__ == '__main__':
arr = [ "catgc", "ctaagt", "gcta", "ttca", "atgcatc" ]
print("The Shortest Superstring is " + shortestSuperstring(arr))
|
C#
using System;
using System.Collections.Generic;
class Program
{
static int CalcOverlap(string a, string b)
{
for (int i = 1; i < a.Length; i++)
{
if (b.IndexOf(a.Substring(i)) == 0)
{
return b.Length - a.Length + i;
}
}
return b.Length;
}
static string ShortestSuperstring(List<string> A)
{
int n = A.Count;
int[,] graph = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
graph[i, j] = CalcOverlap(A[i], A[j]);
graph[j, i] = CalcOverlap(A[j], A[i]);
}
}
int[][] dp = new int[1 << n][];
int[][] path = new int[1 << n][];
int last = -1, minVal = int.MaxValue;
for (int i = 0; i < (1 << n); i++)
{
dp[i] = new int[n];
path[i] = new int[n];
for (int j = 0; j < n; j++)
{
dp[i][j] = int.MaxValue;
}
}
for (int mask = 1; mask < (1 << n); mask++)
{
for (int j = 0; j < n; j++)
{
if ((mask & (1 << j)) > 0)
{
int prevMask = mask - (1 << j);
if (prevMask == 0)
{
dp[mask][j] = A[j].Length;
}
else
{
for (int k = 0; k < n; k++)
{
if (dp[prevMask][k] < int.MaxValue &&
dp[prevMask][k] + graph[k, j] < dp[mask][j])
{
dp[mask][j] = dp[prevMask][k] + graph[k, j];
path[mask][j] = k;
}
}
}
}
if (mask == (1 << n) - 1 && dp[mask][j] < minVal)
{
minVal = dp[mask][j];
last = j;
}
}
}
string res = string.Empty;
int currentMask = (1 << n) - 1;
Stack<int> s = new Stack<int>();
while (currentMask > 0)
{
s.Push(last);
int tempMask = currentMask;
currentMask -= (1 << last);
last = path[tempMask][last];
}
int firstStringIndex = s.Pop();
res += A[firstStringIndex];
while (s.Count > 0)
{
int nextStringIndex = s.Pop();
res += A[nextStringIndex].
Substring(A[nextStringIndex].Length - graph[firstStringIndex,
nextStringIndex]);
firstStringIndex = nextStringIndex;
}
return res;
}
static void Main()
{
List<string> arr = new List<string> { "catgc", "ctaagt", "gcta", "ttca", "atgcatc" };
Console.WriteLine("The Shortest Superstring is " + ShortestSuperstring(arr));
}
}
|
Javascript
function shortestSuperstring(A) {
let n = A.length;
let graph = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
graph[i][j] = calc(A[i], A[j]);
graph[j][i] = calc(A[j], A[i]);
}
}
let dp = new Array(1 << n).fill(0).map(() => new Array(n).fill(0));
let path = new Array(1 << n).fill(0).map(() => new Array(n).fill(0));
let last = -1, min = Number.MAX_VALUE;
for (let i = 1; i < (1 << n); i++) {
dp[i].fill(Number.MAX_VALUE);
for (let j = 0; j < n; j++) {
if ((i & (1 << j)) > 0) {
let prev = i - (1 << j);
if (prev == 0) {
dp[i][j] = A[j].length;
} else {
for (let k = 0; k < n; k++) {
if (dp[prev][k] < Number.MAX_VALUE && dp[prev][k] + graph[k][j] < dp[i][j]) {
dp[i][j] = dp[prev][k] + graph[k][j];
path[i][j] = k;
}
}
}
}
if (i == (1 << n) - 1 && dp[i][j] < min) {
min = dp[i][j];
last = j;
}
}
}
let sb = "";
let cur = (1 << n) - 1;
let stack = [];
while (cur > 0) {
stack.push(last);
let temp = cur;
cur -= (1 << last);
last = path[temp][last];
}
let i = stack.pop();
sb += A[i];
while (stack.length > 0) {
let j = stack.pop();
sb += A[j].substring(A[j].length - graph[i][j]);
i = j;
}
return sb;
}
function calc(a, b) {
for (let i = 1; i < a.length; i++) {
if (b.startsWith(a.substring(i))) {
return b.length - a.length + i;
}
}
return b.length;
}
let arr = ["catgc", "ctaagt", "gcta", "ttca", "atgcatc"];
console.log("The Shortest Superstring is " + shortestSuperstring(arr));
|
Output
The Shortest Superstring is gctaagttcatgcatc
Time complexity: O(n^2 * 2^n), where N is the length of the string array.
Auxiliary Space: O(2^N * N).
There exist better approximate algorithms for this problem. Please refer to below link.
Shortest Superstring Problem | Set 2 (Using Set Cover)
Another Approach Using Bitmask and Dynamic Programming:
This is actually bitmasking problem: if we look at our strings as nodes, then we can evaluate distance between one string and another, for example for abcde and cdefghij distance is 5, because we need to use 5 more symbols fghij to continue first string to get the second. Note, that this is not symmetric, so our graph is oriented.
Java
import java.io.*;
import java.util.*;
class Solution
{
public static String shortestSuperstring(String[] words) {
int n = words.length;
int[][] distance = new int[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int min = Math.min(words[i].length(), words[j].length());
for(int k=min; k>=0; k--){
if(words[i].endsWith(words[j].substring(0,k))) {
distance[i][j] = words[j].length() - k;
break;
}
}
}
}
int dp[][] = new int[(1<<n)][n];
int path[][] = new int[(1<<n)][n];
String ans = "";
int len = Integer.MAX_VALUE;
for(int i = 0; i<n; i++){
for(int j=0; j< ( 1<<n); j++){
Arrays.fill(dp[j], -1);
Arrays.fill(path[j], -1);
}
int tsp = tsp(i, 0, distance, dp, path, n);
String str = createPath(words, i, distance, path);
if(str.length() < len){
ans = str;
len = str.length();
}
}
return ans;
}
private static int tsp(int city, int mask, int[][] distance, int[][] dp, int[][] path, int n){
if(mask == ((1<<n) - 1)) return 0;
if(dp[mask][city] != -1){
return dp[mask][city];
}
int ans = Integer.MAX_VALUE;
int nextCity = -1;
for(int i = 0; i<n; i++){
if((mask & (1<<i)) == 0 ){
int dis = distance[city][i] + tsp(i, (mask | (1<<i)), distance, dp, path, n);
if(dis < ans){
ans = dis;
nextCity = i;
}
}
}
path[mask][city] = nextCity;
dp[mask][city] = ans;
return ans;
}
private static String createPath(String[] words, int start, int[][] distance, int[][] path){
int c = start;
StringBuilder sb = new StringBuilder(words);
int mask = (1<<start);
int x = path[mask];
while(x != -1){
sb.append(words[x].substring(words[x].length() - distance[x]));
mask |= (1<<x);
c = x;
x = path[mask][x];
}
return sb.toString();
}
public static void main(String[] args)
{
String[] arr = { "catgc", "ctaagt",
"gcta", "ttca", "atgcatc" };
System.out.println("The Shortest Superstring is " +
shortestSuperstring(arr));
}
}
|
Python
def shortest_superstring(words):
n = len(words)
def calc_overlap(a, b):
min_len = min(len(a), len(b))
for k in range(min_len, -1, -1):
if a.endswith(b[:k]):
return len(b) - k
return len(b)
distance = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
distance[i][j] = calc_overlap(words[i], words[j])
dp = [[float('inf')] * n for _ in range(1 << n)]
path = [[-1] * n for _ in range(1 << n)]
ans = ""
min_len = float('inf')
for i in range(n):
for j in range(1 << n):
dp[j] = [-1] * n
path[j] = [-1] * n
tsp_value = tsp(i, 1 << i, distance, dp, path, n)
superstring = create_path(words, i, distance, path)
if len(superstring) < min_len:
ans = superstring
min_len = len(superstring)
return ans
def tsp(city, mask, distance, dp, path, n):
if mask == (1 << n) - 1:
return 0
if dp[mask][city] != -1:
return dp[mask][city]
ans = float('inf')
next_city = -1
for i in range(n):
if not (mask & (1 << i)):
dis = distance[city][i] + tsp(i, mask | (1 << i), distance, dp, path, n)
if dis < ans:
ans = dis
next_city = i
path[mask][city] = next_city
dp[mask][city] = ans
return ans
def create_path(words, start, distance, path):
c = start
sb = [words]
mask = 1 << start
x = path[mask]
while x != -1:
sb.append(words[x][-(distance[x]):])
mask |= (1 << x)
c = x
x = path[mask][x]
return "".join(sb)
arr = ["catgc", "ctaagt", "gcta", "ttca", "atgcatc"]
result = shortest_superstring(arr)
print("The Shortest Superstring is", result)
|
Javascript
function shortestSuperstring(words) {
const n = words.length;
function calcOverlap(a, b) {
const minLen = Math.min(a.length, b.length);
for (let k = minLen; k >= 0; k--) {
if (a.endsWith(b.substring(0, k))) {
return b.length - k;
}
}
return b.length;
}
const distance = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
distance[i][j] = calcOverlap(words[i], words[j]);
}
}
const dp = new Array(1 << n).fill(0).map(() => new Array(n).fill(Infinity));
const path = new Array(1 << n).fill(0).map(() => new Array(n).fill(-1));
let ans = "";
let minLen = Infinity;
for (let i = 0; i < n; i++) {
for (let j = 0; j < (1 << n); j++) {
dp[j] = new Array(n).fill(-1);
path[j] = new Array(n).fill(-1);
}
const tspValue = tsp(i, 1 << i, distance, dp, path, n);
const superstring = createPath(words, i, distance, path);
if (superstring.length < minLen) {
ans = superstring;
minLen = superstring.length;
}
}
return ans;
}
function tsp(city, mask, distance, dp, path, n) {
if (mask === (1 << n) - 1) {
return 0;
}
if (dp[mask][city] !== -1) {
return dp[mask][city];
}
let ans = Infinity;
let nextCity = -1;
for (let i = 0; i < n; i++) {
if (!(mask & (1 << i))) {
const dis = distance[city][i] + tsp(i, mask | (1 << i), distance, dp, path, n);
if (dis < ans) {
ans = dis;
nextCity = i;
}
}
}
path[mask][city] = nextCity;
dp[mask][city] = ans;
return ans;
}
function createPath(words, start, distance, path) {
let c = start;
const sb = [words];
let mask = 1 << start;
let x = path[mask];
while (x !== -1) {
sb.push(words[x].substring(words[x].length - distance[x]));
mask |= 1 << x;
c = x;
x = path[mask][x];
}
return sb.join("");
}
const arr = ["catgc", "ctaagt", "gcta", "ttca", "atgcatc"];
const result = shortestSuperstring(arr);
console.log("The Shortest Superstring is", result);
|
Output
The Shortest Superstring is gctaagttcatgcatc
Time complexity: O(2^n*n^2*M), where M is the length of answer
Auxiliary Space: O(2^n*n*M) as well.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!