943. Find the Shortest Superstring LeetCode Solution
In this guide, you will get 943. Find the Shortest Superstring LeetCode Solution with the best time and space complexity. The solution to Find the Shortest Superstring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
Complexity Analysis
Time Complexity: O(n!)
Space Complexity: O(n!)
943. Find the Shortest Superstring LeetCode Solution in C++
class Solution {
public:
string shortestSuperstring(vector<string>& words) {
const int n = words.size();
// cost[i][j] := the cost to append words[j] after words[i]
vector<vector<int>> cost(n, vector<int>(n));
// Returns the cost to append b after a.
auto getCost = [](const string& a, const string& b) {
int cost = b.length();
const int minLength = min(a.length(), b.length());
for (int k = 1; k <= minLength; ++k)
if (a.substr(a.length() - k) == b.substr(0, k))
cost = b.length() - k;
return cost;
};
// Pre-calculate cost array to save time.
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
cost[i][j] = getCost(words[i], words[j]);
cost[j][i] = getCost(words[j], words[i]);
}
vector<int> bestPath;
int minLength = n * 20; // given by problem
dfs(words, cost, {}, bestPath, 0, 0, 0, minLength);
string ans = words[bestPath[0]];
for (int k = 1; k < n; ++k) {
const int i = bestPath[k - 1];
const int j = bestPath[k];
ans += words[j].substr(words[j].length() - cost[i][j]);
}
return ans;
}
private:
// used: i-th bit means words[i] is used or not
void dfs(const vector<string>& words, const vector<vector<int>>& cost,
vector<int>&& path, vector<int>& bestPath, int used, int depth,
int currLength, int& minLength) {
if (currLength >= minLength)
return;
if (depth == words.size()) {
minLength = currLength;
bestPath = path;
return;
}
for (int i = 0; i < words.size(); ++i) {
if (used >> i & 1)
continue;
path.push_back(i);
const int newLength = depth == 0 ? words[i].length()
: currLength + cost[path[depth - 1]][i];
dfs(words, cost, std::move(path), bestPath, used | 1 << i, depth + 1,
newLength, minLength);
path.pop_back();
}
}
}; /* code provided by PROGIEZ */
943. Find the Shortest Superstring LeetCode Solution in Java
class Solution {
public String shortestSuperstring(String[] words) {
final int n = words.length;
// cost[i][j] := the cost to append words[j] after words[i]
int[][] cost = new int[n][n];
// Pre-calculate cost array to save time.
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
cost[i][j] = getCost(words[i], words[j]);
cost[j][i] = getCost(words[j], words[i]);
}
List<Integer> path = new ArrayList<>();
List<Integer> bestPath = new ArrayList<>();
minLength = n * 20; // given by problem
dfs(words, cost, path, bestPath, 0, 0, 0);
StringBuilder sb = new StringBuilder(words[bestPath.get(0)]);
for (int k = 1; k < n; ++k) {
final int i = bestPath.get(k - 1);
final int j = bestPath.get(k);
sb.append(words[j].substring(words[j].length() - cost[i][j]));
}
return sb.toString();
}
private int minLength;
// Returns the cost to append b after a.
private int getCost(final String a, final String b) {
int cost = b.length();
final int minLength = Math.min(a.length(), b.length());
for (int k = 1; k <= minLength; ++k)
if (a.substring(a.length() - k).equals(b.substring(0, k)))
cost = b.length() - k;
return cost;
}
// used: i-th bit means words[i] is used or not
private void dfs(String[] words, int[][] cost, List<Integer> path, List<Integer> bestPath,
int used, int depth, int currLength) {
if (currLength >= minLength)
return;
if (depth == words.length) {
minLength = currLength;
bestPath.clear();
for (final int node : path) {
bestPath.add(node);
}
return;
}
for (int i = 0; i < words.length; ++i) {
if ((used >> i & 1) == 1)
continue;
path.add(i);
final int newLength =
depth == 0 ? words[i].length() : currLength + cost[path.get(depth - 1)][i];
dfs(words, cost, path, bestPath, used | 1 << i, depth + 1, newLength);
path.remove(path.size() - 1);
}
}
} // code provided by PROGIEZ
943. Find the Shortest Superstring LeetCode Solution in Python
class Solution {
public:
string shortestSuperstring(vector<string>& words) {
const int n = words.size();
// cost[i][j] := the cost to append words[j] after words[i]
vector<vector<int>> cost(n, vector<int>(n));
// dp[s][j] := the minimum cost to visit nodes of s ending in j, s is a
// binary Value, e.g. dp[6][2] means the minimum cost to visit {1, 2} ending
// in 2 (6 = 2^1 + 2^2)
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));
// parent[s][j] := the parent of "nodes of s ending in j"
vector<vector<int>> parent(1 << n, vector<int>(n, -1));
// Returns the cost to append b after a.
auto getCost = [](const string& a, const string& b) {
int cost = b.length();
const int minLength = min(a.length(), b.length());
for (int k = 1; k <= minLength; ++k)
if (a.substr(a.length() - k) == b.substr(0, k))
cost = b.length() - k;
return cost;
};
// Pre-calculate the `cost` array to save time.
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
cost[i][j] = getCost(words[i], words[j]);
cost[j][i] = getCost(words[j], words[i]);
}
for (int i = 0; i < n; ++i)
dp[1 << i][i] = words[i].length();
// Enumerate all the states ending in different nodes.
for (int s = 1; s < (1 << n); ++s)
for (int i = 0; i < n; ++i) {
if ((s & (1 << i)) == 0)
continue;
for (int j = 0; j < n; ++j)
if (dp[s - (1 << i)][j] + cost[j][i] < dp[s][i]) {
dp[s][i] = dp[s - (1 << i)][j] + cost[j][i];
parent[s][i] = j;
}
}
string ans;
const vector<int>& dpBack = dp.back();
int j = distance(dpBack.begin(), ranges::min_element(dpBack));
int s = (1 << n) - 1; // 2^0 + 2^1 + ... + 2^(n - 1)
// Traverse back to build the string.
while (s > 0) {
const int i = parent[s][j];
if (i == -1)
ans = words[j] + ans;
else
ans = words[j].substr(words[j].length() - cost[i][j]) + ans;
s -= 1 << j;
j = i;
}
return ans;
}
}; # code by PROGIEZ
