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
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) {
8 int max_overlap = 0;
9 for (int i = 0; i < a.size(); ++i) {
10 if (b.find(a.substr(i)) == 0) {
11 max_overlap = a.size() - i;
12 break;
13 }
14 }
15 return max_overlap;
16}
17
18string shortestSuperstring(vector<string>& words) {
19 int n = words.size();
20 vector<vector<int>> overlaps(n, vector<int>(n, 0));
21
22 for (int i = 0; i < n; ++i) {
23 for (int j = 0; j < n; ++j) {
24 if (i != j) {
25 overlaps[i][j] = calculate_overlap(words[i], words[j]);
26 }
27 }
28 }
29
30 int max_mask = 1 << n;
31 vector<vector<int>> dp(max_mask, vector<int>(n, 0));
32 vector<vector<int>> parent(max_mask, vector<int>(n, -1));
33
34 for (int mask = 1; mask < max_mask; ++mask) {
35 for (int u = 0; u < n; ++u) {
36 if ((mask & (1 << u)) == 0) continue;
37 int prev_mask = mask ^ (1 << u);
38
39 if (prev_mask == 0) continue;
40
41 for (int v = 0; v < n; ++v) {
42 if ((prev_mask & (1 << v)) == 0) continue;
43 int val = dp[prev_mask][v] + overlaps[v][u];
44 if (val > dp[mask][u]) {
45 dp[mask][u] = val;
46 parent[mask][u] = v;
47 }
48 }
49 }
50 }
51
52 int max_overlap = 0, last = 0;
53 for (int i = 0; i < n; ++i) {
54 if (dp[max_mask - 1][i] > max_overlap) {
55 max_overlap = dp[max_mask - 1][i];
56 last = i;
57 }
58 }
59
60 vector<int> perm;
61 int mask = max_mask - 1;
62 while (last != -1) {
63 perm.push_back(last);
64 int temp = last;
65 last = parent[mask][last];
66 mask ^= (1 << temp);
67 }
68
69 reverse(perm.begin(), perm.end());
70
71 string result = words[perm[0]];
72 for (int i = 1; i < perm.size(); ++i) {
73 int overlap_len = overlaps[perm[i - 1]][perm[i]];
74 result += words[perm[i]].substr(overlap_len);
75 }
76
77 return result;
78}
79
80int main() {
81 vector<string> words = {"catg", "ctaagt", "gcta", "ttca", "atgcatc"};
82 cout << shortestSuperstring(words) << endl;
83 return 0;
84}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.
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.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4#define MAX 12
5
6bool used[MAX];
7char result[255];
8
9void findOverlap(char *a, char *b, char *res) {
10 int maxOverlap = 0;
11 int len1 = strlen(a), len2 = strlen(b);
12 for (int i = 1; i <= len1 && i <= len2; i++) {
13 if (strncmp(a + len1 - i, b, i) == 0) {
14 maxOverlap = i;
15 }
16 }
17 sprintf(res, "%.*s%s", len1 - maxOverlap, a, b);
18}
19
20void permute(char words[][21], int n, char superStr[255], int len, char minSuperStr[255], int *minLen) {
21 if (len >= *minLen) return;
22
23 bool allUsed = true;
24 for (int i = 0; i < n; i++) {
25 if (!used[i]) {
26 allUsed = false;
27 used[i] = true;
28
29 if (len == 0) {
30 strcpy(superStr, words[i]);
31 permute(words, n, superStr, strlen(words[i]), minSuperStr, minLen);
32 } else {
33 char temp[255];
34 findOverlap(superStr, words[i], temp);
35 int tempLen = strlen(temp);
36 permute(words, n, temp, tempLen, minSuperStr, minLen);
37 }
38
39 used[i] = false;
40 }
41 }
42 if (allUsed && len < *minLen) {
43 *minLen = len;
44 strcpy(minSuperStr, superStr);
45 }
46}
47
48char *shortestSuperstring(char words[][21], int wordsSize) {
49 char minSuperStr[255];
50 int minLen = 1000;
51 memset(used, false, sizeof(used));
52
53 permute(words, wordsSize, result, 0, minSuperStr, &minLen);
54
55 return strdup(minSuperStr);
56}
57
58int main() {
59 char words[][21] = {"alex","loves","leetcode"};
60 int wordsSize = sizeof(words) / sizeof(words[0]);
61
62 printf("%s\n", shortestSuperstring(words, wordsSize));
63 return 0;
64}
65This C program defines a function shortestSuperstring that uses permutation and greedy approach to find the shortest superstring for the given array of words. The auxiliary function findOverlap calculates maximum overlap between two strings and constructs a new string by overlapping. The permute function generates permutations and keeps track of the shortest constructed superstring.
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.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5#define MAX_WORDS 12
6#define MAX_WORD_LENGTH 20
7#define INF 999999
8
9int overlap[MAX_WORDS][MAX_WORDS];
10int dp[1 << MAX_WORDS][MAX_WORDS];
11int parent[1 << MAX_WORDS][MAX_WORDS];
12
13int calculateOverlap(char *a, char *b) {
14 int maxOverlap = 0;
15 int len1 = strlen(a), len2 = strlen(b);
16 for (int i = 1; i <= len1 && i <= len2; ++i) {
17 if (strncmp(a + len1 - i, b, i) == 0) {
18 maxOverlap = i;
19 }
20 }
21 return maxOverlap;
22}
23
24void constructPath(int last, int mask, int wordsSize, char words[MAX_WORDS][MAX_WORD_LENGTH + 1], char* res) {
25 int index = 0;
26 int bitmask = (1 << wordsSize) - 1;
27 while (mask != 0) {
28 int curr = last;
29 int prev = parent[mask][curr];
30
31 int overlapLen = (prev == -1) ? 0 : overlap[prev][curr];
32 if (prev != -1) {
33 strcat(res, words[curr] + overlapLen);
34 index = strlen(res);
35 } else {
36 strcpy(res, words[curr]);
37 }
38
39 mask ^= (1 << curr);
40 last = prev;
41 }
42
43 // Reverse the res array
44 int len = strlen(res);
45 for (int i = 0; i < len / 2; ++i) {
46 char temp = res[i];
47 res[i] = res[len - i - 1];
48 res[len - i - 1] = temp;
49 }
50}
51
52char *shortestSuperstring(char words[MAX_WORDS][MAX_WORD_LENGTH + 1], int wordsSize) {
53 memset(dp, INF, sizeof(dp));
54 for (int i = 0; i < wordsSize; ++i) {
55 for (int j = 0; j < wordsSize; ++j) {
56 if (i != j) {
57 overlap[i][j] = calculateOverlap(words[i], words[j]);
58 }
59 }
60 }
61
62 for (int i = 0; i < wordsSize; ++i) {
63 dp[1 << i][i] = (int)strlen(words[i]);
64 }
65
66 for (int mask = 0; mask < (1 << wordsSize); ++mask) {
67 for (int i = 0; i < wordsSize; ++i) {
68 if (mask & (1 << i)) {
69 for (int j = 0; j < wordsSize; ++j) {
70 if (i != j && (mask & (1 << j))) {
71 int nextMask = mask ^ (1 << i);
72 int currCost = dp[nextMask][j] + (int)strlen(words[i]) - overlap[j][i];
73 if (currCost < dp[mask][i]) {
74 dp[mask][i] = currCost;
75 parent[mask][i] = j;
76 }
77 }
78 }
79 }
80 }
81 }
82
83 int minLength = INF, last = -1;
84 for (int i = 0; i < wordsSize; ++i) {
85 if (dp[(1 << wordsSize) - 1][i] < minLength) {
86 minLength = dp[(1 << wordsSize) - 1][i];
87 last = i;
88 }
89 }
90
91 char *res = malloc(255 * sizeof(char));
92 memset(res, 0, 255);
93 constructPath(last, (1 << wordsSize) - 1, wordsSize, words, res);
94
95 return res;
96}
97
98int main() {
99 char words[MAX_WORDS][MAX_WORD_LENGTH + 1] = {"alex", "loves", "leetcode"};
100 int wordsSize = 3;
101
102 char *result = shortestSuperstring(words, wordsSize);
103 printf("%s\n", result);
104 free(result);
105
106 return 0;
107}
108This C solution applies dynamic programming and bitmasking to calculate the shortest superstring. The method constructs a graph where nodes represent words, and edges express overlaps. By treating the problem as a TSP, the dp array is used to store minimum path lengths, leveraging overlap calculations to optimize transitions.