Sponsored
Sponsored
This approach uses dynamic programming with bitmasking to explore all subsets of the strings. The dynamic programming state dp[mask][i] is the shortest superstring for the subset of words represented by the bitmask 'mask' ending with the 'i-th' string. By iterating through all possible states and updating them based on the previously computed states, we determine the shortest superstring that includes all words. The final superstring is constructed by backtracking through the computed states.
Time Complexity: O(n^2 * 2^n) where n is the number of words. This is because there are 2^n subsets and each subset operation can have O(n^2) complexity for managing overlaps.
Space Complexity: O(n * 2^n) for storing DP and path arrays.
1def shortestSuperstring(words):
2 n = len(words)
3
4 # Calculate the overlap between two strings
5 def get_overlap(a, b):
6 max_overlap = 0
7 for i in range(len(a)):
8 if b.startswith(a[i:]):
9 max_overlap = len(a) - i
10 break
11 return max_overlap
12
13 overlaps = [[0] * n for _ in range(n)]
14 for i in range(n):
15 for j in range(n):
16 if i != j:
17 overlaps[i][j] = get_overlap(words[i], words[j])
18
19 dp = [[0] * n for _ in range(1 << n)]
20 path = [[-1] * n for _ in range(1 << n)]
21
22 for mask in range(1, 1 << n):
23 for bit in range(n):
24 if (mask >> bit) & 1:
25 prev_mask = mask ^ (1 << bit)
26 if prev_mask == 0:
27 continue
28 for i in range(n):
29 if (prev_mask >> i) & 1:
30 value = dp[prev_mask][i] + overlaps[i][bit]
31 if value > dp[mask][bit]:
32 dp[mask][bit] = value
33 path[mask][bit] = i
34
35 max_overlap = max(dp[-1])
36 last = dp[-1].index(max_overlap)
37
38 mask = (1 << n) - 1
39 perm = []
40 while last != -1:
41 perm.append(last)
42 temp = last
43 last = path[mask][last]
44 mask ^= (1 << temp)
45
46 perm = perm[::-1]
47
48 answer = words[perm[0]]
49 for i in range(1, len(perm)):
50 overlap_len = overlaps[perm[i - 1]][perm[i]]
51 answer += words[perm[i]][overlap_len:]
52
53 return answer
54
55# Example usage
56words = ["catg", "ctaagt", "gcta", "ttca", "atgcatc"]
57print(shortestSuperstring(words))The Python solution calculates the maximum overlap for every pair of strings and uses dynamic programming to find the shortest superstring that can be constructed. Overlaps are computed once and stored in a 2D list "overlaps". The dp table keeps track of the optimal solution for every subset of strings represented by a bitmask, and backtracking on this table gives the final superstring.
This approach translates the problem into a variant of the Travelling Salesman Problem (TSP) where the cities correspond to the strings and the distances between them are the inverse of the overlap size. The solution can use heuristics to find a short path that visits all the 'cities' once, effectively creating the shortest superstring. Since exact TSP is NP-hard, approximation algorithms or heuristics can speed up finding a good solution.
Time Complexity: O(n^2 * 2^n), where n is the number of strings. This is due to calculating overlaps for every pair and iterating over all subsets.
Space Complexity: O(n * 2^n) for storing DP tables.
1#include <iostream>
2#include <vector>
3#include <string>
4#include <limits.h>
5using namespace std;
6
7int calculate_overlap(string a, string b) {
int max_overlap = 0;
for (int i = 0; i < a.size(); ++i) {
if (b.find(a.substr(i)) == 0) {
max_overlap = a.size() - i;
break;
}
}
return max_overlap;
}
string shortestSuperstring(vector<string>& words) {
int n = words.size();
vector<vector<int>> overlaps(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j) {
overlaps[i][j] = calculate_overlap(words[i], words[j]);
}
}
}
int max_mask = 1 << n;
vector<vector<int>> dp(max_mask, vector<int>(n, 0));
vector<vector<int>> parent(max_mask, vector<int>(n, -1));
for (int mask = 1; mask < max_mask; ++mask) {
for (int u = 0; u < n; ++u) {
if ((mask & (1 << u)) == 0) continue;
int prev_mask = mask ^ (1 << u);
if (prev_mask == 0) continue;
for (int v = 0; v < n; ++v) {
if ((prev_mask & (1 << v)) == 0) continue;
int val = dp[prev_mask][v] + overlaps[v][u];
if (val > dp[mask][u]) {
dp[mask][u] = val;
parent[mask][u] = v;
}
}
}
}
int max_overlap = 0, last = 0;
for (int i = 0; i < n; ++i) {
if (dp[max_mask - 1][i] > max_overlap) {
max_overlap = dp[max_mask - 1][i];
last = i;
}
}
vector<int> perm;
int mask = max_mask - 1;
while (last != -1) {
perm.push_back(last);
int temp = last;
last = parent[mask][last];
mask ^= (1 << temp);
}
reverse(perm.begin(), perm.end());
string result = words[perm[0]];
for (int i = 1; i < perm.size(); ++i) {
int overlap_len = overlaps[perm[i - 1]][perm[i]];
result += words[perm[i]].substr(overlap_len);
}
return result;
}
int main() {
vector<string> words = {"catg", "ctaagt", "gcta", "ttca", "atgcatc"};
cout << shortestSuperstring(words) << endl;
return 0;
}This approach involves generating all permutations of the words and computing the shortest superstring by calculating overlaps greedily. We concatenate each pair of words in the permutation, reducing the length by maximizing the overlap between consecutive strings. This brute force method is feasible with a small number of words due to its factorial time complexity but ensures the optimal solution is found.
Time Complexity: O(n! * len^2) where n is the number of words and len is the average length of words.
Space Complexity: O(n * len) for storing intermediate permutations and results.
using System.Collections.Generic;
using System.Linq;
class Program
{
static string FindOverlap(string a, string b)
{
int maxOverlap = 0;
int len1 = a.Length, len2 = b.Length;
for (int i = 1; i <= len1 && i <= len2; i++)
{
if (a.Substring(len1 - i, i) == b.Substring(0, i))
{
maxOverlap = i;
}
}
return a.Substring(0, len1 - maxOverlap) + b;
}
static void Permute(string[] words, bool[] used, int depth, ref string superStr, ref string minSuperStr)
{
if (superStr.Length >= minSuperStr.Length) return;
if (depth == words.Length)
{
if (superStr.Length < minSuperStr.Length)
{
minSuperStr = superStr;
}
return;
}
for (int i = 0; i < words.Length; i++)
{
if (!used[i])
{
used[i] = true;
string originalSuperStr = superStr;
if (superStr.Length == 0)
{
superStr = words[i];
}
else
{
superStr = FindOverlap(superStr, words[i]);
}
Permute(words, used, depth + 1, ref superStr, ref minSuperStr);
superStr = originalSuperStr;
used[i] = false;
}
}
}
public static string ShortestSuperstring(string[] words)
{
string minSuperStr = string.Join("", words);
string superStr = "";
bool[] used = new bool[words.Length];
Permute(words, used, 0, ref superStr, ref minSuperStr);
return minSuperStr;
}
static void Main()
{
string[] words = { "alex", "loves", "leetcode" };
Console.WriteLine(ShortestSuperstring(words));
}
}
This approach models the problem using dynamic programming with a bitmask and Traveling Salesman Problem (TSP) style optimization. By representing used words as a bitmask, we systematically build the shortest superstring by adding each word while maximizing overlaps, applying dynamic programming to store and reuse results of subproblems.
Time Complexity: O(n^2 * 2^n) due to combination of all subsets and pairwise overlaps.
Space Complexity: O(n * 2^n) for dp and parent tracking arrays.
using System.Collections.Generic;
class Program
{
private static int CalculateOverlap(string a, string b)
{
int maxOverlap = 0;
for (int i = 1; i <= Math.Min(a.Length, b.Length); i++)
{
if (a.Substring(a.Length - i) == b.Substring(0, i))
{
maxOverlap = i;
}
}
return maxOverlap;
}
public static string ShortestSuperstring(string[] words)
{
int n = words.Length;
int[][] overlap = new int[n][];
for (int i = 0; i < n; i++)
{
overlap[i] = new int[n];
for (int j = 0; j < n; j++)
{
overlap[i][j] = CalculateOverlap(words[i], words[j]);
}
}
int[][] dp = new int[1 << n][];
int[][] parent = new int[1 << n][];
for (int i = 0; i < (1 << n); i++)
{
dp[i] = new int[n];
parent[i] = new int[n];
Array.Fill(dp[i], int.MaxValue / 2);
Array.Fill(parent[i], -1);
}
for (int i = 0; i < n; i++)
{
dp[1 << i][i] = words[i].Length;
}
for (int mask = 0; mask < (1 << n); mask++)
{
for (int i = 0; i < n; i++)
{
if ((mask & (1 << i)) != 0)
{
for (int j = 0; j < n; j++)
{
if (i != j && (mask & (1 << j)) != 0)
{
int prevMask = mask ^ (1 << i);
int currLength = dp[prevMask][j] + words[i].Length - overlap[j][i];
if (currLength < dp[mask][i])
{
dp[mask][i] = currLength;
parent[mask][i] = j;
}
}
}
}
}
}
int minLength = int.MaxValue;
int last = -1;
for (int i = 0; i < n; i++)
{
if (dp[(1 << n) - 1][i] < minLength)
{
minLength = dp[(1 << n) - 1][i];
last = i;
}
}
List<int> path = new List<int>();
int mask = (1 << n) - 1;
while (mask != 0)
{
path.Add(last);
int temp = parent[mask][last];
mask ^= 1 << last;
last = temp;
}
path.Reverse();
string superstring = words[path[0]];
for (int i = 1; i < path.Count; i++)
{
int j = path[i];
int overlapLen = overlap[path[i - 1]][j];
superstring += words[j].Substring(overlapLen);
}
return superstring;
}
static void Main()
{
string[] words = { "alex", "loves", "leetcode" };
Console.WriteLine(ShortestSuperstring(words));
}
}
This C++ solution uses a dynamical approach similar to TSP by using bitmasks to represent subsets of words. The overlap between strings is used to define "distances", and the algorithm tries to maximize the overlap, effectively minimizing the path length, or the resulting superstring length. The "cost" or path length is maximized by summing up the overlaps between consecutive elements in permutations.
In C#, this solution explores all possible orders of words to construct superstrings by recursively invoking Permute. The FindOverlap method calculates overlaps, reducing unnecessary length in the superstring. The shortest valid combination is tracked and returned.
This C# program models the shortest superstring problem using a dynamic programming approach similar to solving a TSP problem with bitmask optimization. Overlaps define transition weights, and dp arrays store optimal path information for generating the shortest superstring at the end.