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"
```
Solution 1 : Search + Pruning¶
Try all permutations. Pre-process the cost from word[i] to word[j] and store it in g[i][j].
Time complexity: \(O(n!)\) Space complexity: \(O(n)\)
// 439 ms, 35.8MB
class Solution {
private int n;
private int[][] g;
private String[] a;
private int best_len;
private int[] path;
private int[] best_path;
private void dfs(int d, int used, int cur_len) {
if (cur_len >= best_len) return;
if (d == n) {
best_len = cur_len;
best_path = path.clone();
return;
}
for (int i = 0; i < n; ++i) {
if ((used & (1 << i)) != 0) continue;
path[d] = i;
dfs(d + 1,
used | (1 << i),
d == 0 ? a[i].length() : cur_len + g[path[d - 1]][i]);
}
}
public String shortestSuperstring(String[] A) {
n = A.length;
g = new int[n][n];
a = A;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
g[i][j] = A[j].length();
for (int k = 1; k <= Math.min(A[i].length(), A[j].length()); ++k)
if (A[i].substring(A[i].length() - k).equals(A[j].substring(0, k)))
g[i][j] = A[j].length() - k;
}
path = new int[n];
best_len = Integer.MAX_VALUE;
dfs(0, 0, 0);
String ans = A[best_path[0]];
for (int k = 1; k < n; ++k) {
int i = best_path[k - 1];
int j = best_path[k];
ans += A[j].substring(A[j].length() - g[i][j]);
}
return ans;
}
}
Solution 2: DP¶
g[i][j] is the cost of appending word[j] after word[i], or weight of edge[i][j].
We would like find the shortest path to visit each node from 0 to n – 1 once and only once this is called the Travelling sells man’s problem which is NP-Complete.
We can solve it with DP that uses exponential time.
dp[s][i] := min distance to visit nodes (represented as a binary state s) once and only once and the path ends with node i.
e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1, the possible paths could be (0, 2, 1), (2, 0, 1).
Time complexity: \(O(n^2 * 2^n)\) Space complexity: \(O(n * 2^n)\)
// running time: 20 ms
class Solution {
public:
string shortestSuperstring(vector<string>& A) {
const int n = A.size();
vector<vector<int>> g(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
g[i][j] = A[j].length();
for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)
if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))
g[i][j] = A[j].length() - k;
}
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));
vector<vector<int>> parent(1 << n, vector<int>(n, -1));
for (int i = 0; i < n; ++i) dp[1 << i][i] = A[i].length();
for (int s = 1; s < (1 << n); ++s) {
for (int j = 0; j < n; ++j) {
if (!(s & (1 << j))) continue;
int ps = s & ~(1 << j);
for (int i = 0; i < n; ++i) {
if (dp[ps][i] + g[i][j] < dp[s][j]) {
dp[s][j] = dp[ps][i] + g[i][j];
parent[s][j] = i;
}
}
}
}
auto it = min_element(begin(dp.back()), end(dp.back()));
int j = it - begin(dp.back());
int s = (1 << n) - 1;
string ans;
while (s) {
int i = parent[s][j];
if (i < 0) ans = A[j] + ans;
else ans = A[j].substr(A[j].length() - g[i][j]) + ans;
s &= ~(1 << j);
j = i;
}
return ans;
}