http://massivealgorithms.blogspot.com/2015/06/travelling-salesman-problem-set-1-naive.html
https://leetcode.com/problems/find-the-shortest-superstring/
Approach 1: Dynamic Programming
(状态压缩动态规划) O(2nn2)O(2nn2)
假设 SS 表示一个集合，设 f(S,i)f(S,i) 表示已经满足了 SS 中的字符串，且结尾的字符串是 A 中的第 ii 个时的最短长度。
转移时，每次枚举一个在 SS 中的字符串 ii 当做结尾 ，然后再枚举一个不在 SS 中的字符串 jj，预处理 ii 的后缀和 jj 的前缀重叠的个数。
初始时，SS 中只加入一个字符串，长度为当前字符串的长度。
答案为以 SS 为全集，以ii 为结尾的字符串中的最小值。
SS 可以用一个二进制数字表示，二进制位为 0 则字符串不存在，为 1 则字符串存在。
最后生成答案是只需要按照动态规划的最优值往回找即可。
时间复杂度
状态数为 O(2nn)O(2nn)，转移需要 O(n)O(n) 的时间，故总时间复杂度为 O(2nn2)O(2nn2)。
https://zhanghuimeng.github.io/post/leetcode-943-find-the-shortest-superstring/
https://www.geeksforgeeks.org/shortest-superstring-problem/
https://www.geeksforgeeks.org/shortest-superstring-problem-set-2-using-set-cover/
https://leetcode.com/problems/find-the-shortest-superstring/
Given an array A of strings, find any smallest string that contains each string in
A as a substring.
We may assume that no string in
A is substring of another string in A.
Example 1:
Input: ["alex","loves","leetcode"] Output: "alexlovesleetcode" Explanation: All permutations of "alex","loves","leetcode" would also be accepted.
Example 2:
Input: ["catg","ctaagt","gcta","ttca","atgcatc"] Output: "gctaagttcatgcatc"
Note:
1 <= A.length <= 121 <= A[i].length <= 20
Approach 1: Dynamic Programming
We have to put the words into a row, where each word may overlap the previous word. This is because no word is contained in any word.
Also, it is sufficient to try to maximize the total overlap of the words.
Say we have put some words down in our row, ending with word
A[i]. Now say we put down word A[j] as the next word, where word j hasn't been put down yet. The overlap increases by overlap(A[i], A[j]).
We can use dynamic programming to leverage this recursion. Let
dp(mask, i) be the total overlap after putting some words down (represented by a bitmask mask), for which A[i] was the last word put down. Then, the key recursion is dp(mask ^ (1<<j), j) = max(overlap(A[i], A[j]) + dp(mask, i)), where the jth bit is not set in mask, and iranges over all bits set in mask.
Of course, this only tells us what the maximum overlap is for each set of words. We also need to remember each choice along the way (ie. the specific
i that made dp(mask ^ (1<<j), j) achieve a minimum) so that we can reconstruct the answer.
Algorithm
Our algorithm has 3 main components:
- Precompute
overlap(A[i], A[j])for all possiblei, j. - Calculate
dp[mask][i], keeping track of the "parent"ifor eachjas described above. - Reconstruct the answer using
parentinformation.
Please see the implementation for more details about each section.
- Time Complexity: , where is the number of words, and is the maximum length of each word.
- Space Complexity: .
public String shortestSuperstring(String[] A) {
int N = A.length;
// Populate overlaps
int[][] overlaps = new int[N][N];
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (i != j) {
int m = Math.min(A[i].length(), A[j].length());
for (int k = m; k >= 0; --k)
if (A[i].endsWith(A[j].substring(0, k))) {
overlaps[i][j] = k;
break;
}
}
// dp[mask][i] = most overlap with mask, ending with ith element
int[][] dp = new int[1 << N][N];
int[][] parent = new int[1 << N][N];
for (int mask = 0; mask < (1 << N); ++mask) {
Arrays.fill(parent[mask], -1);
for (int bit = 0; bit < N; ++bit)
if (((mask >> bit) & 1) > 0) {
// Let's try to find dp[mask][bit]. Previously, we had
// a collection of items represented by pmask.
int pmask = mask ^ (1 << bit);
if (pmask == 0)
continue;
for (int i = 0; i < N; ++i)
if (((pmask >> i) & 1) > 0) {
// For each bit i in pmask, calculate the value
// if we ended with word i, then added word 'bit'.
int val = dp[pmask][i] + overlaps[i][bit];
if (val > dp[mask][bit]) {
dp[mask][bit] = val;
parent[mask][bit] = i;
}
}
}
}
// # Answer will have length sum(len(A[i]) for i) - max(dp[-1])
// Reconstruct answer, first as a sequence 'perm' representing
// the indices of each word from left to right.
int[] perm = new int[N];
boolean[] seen = new boolean[N];
int t = 0;
int mask = (1 << N) - 1;
// p: the last element of perm (last word written left to right)
int p = 0;
for (int j = 0; j < N; ++j)
if (dp[(1 << N) - 1][j] > dp[(1 << N) - 1][p])
p = j;
// Follow parents down backwards path that retains maximum overlap
while (p != -1) {
perm[t++] = p;
seen[p] = true;
int p2 = parent[mask][p];
mask ^= 1 << p;
p = p2;
}
// Reverse perm
for (int i = 0; i < t / 2; ++i) {
int v = perm[i];
perm[i] = perm[t - 1 - i];
perm[t - 1 - i] = v;
}
// Fill in remaining words not yet added
for (int i = 0; i < N; ++i)
if (!seen[i])
perm[t++] = i;
// Reconstruct final answer given perm
StringBuilder ans = new StringBuilder(A[perm[0]]);
for (int i = 1; i < N; ++i) {
int overlap = overlaps[perm[i - 1]][perm[i]];
ans.append(A[perm[i]].substring(overlap));
}
return ans.toString();
}
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)
(状态压缩动态规划) O(2nn2)O(2nn2)
假设 SS 表示一个集合，设 f(S,i)f(S,i) 表示已经满足了 SS 中的字符串，且结尾的字符串是 A 中的第 ii 个时的最短长度。
转移时，每次枚举一个在 SS 中的字符串 ii 当做结尾 ，然后再枚举一个不在 SS 中的字符串 jj，预处理 ii 的后缀和 jj 的前缀重叠的个数。
初始时，SS 中只加入一个字符串，长度为当前字符串的长度。
答案为以 SS 为全集，以ii 为结尾的字符串中的最小值。
SS 可以用一个二进制数字表示，二进制位为 0 则字符串不存在，为 1 则字符串存在。
最后生成答案是只需要按照动态规划的最优值往回找即可。
时间复杂度
状态数为 O(2nn)O(2nn)，转移需要 O(n)O(n) 的时间，故总时间复杂度为 O(2nn2)O(2nn2)。
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;
}
我犯了这些错误：
- 在搞错了状态变量的范围的同时没有设置好变量的初值
- 计算两个字符串的overlap的函数少考虑了一种情况
所以就这样了……
我觉得比较简单的方法还是状态压缩DP。[1]令
dp[mask][i]表示总共包含mask这些字符串，且以A[i]作为结尾的字符串的最小长度（或者最大overlap长度；当字符串都是那么多时，这两者是一样的。然后就可以递推了：dp[mask ^ 1<<j][j] = max(dp[mask][i] + overlap(i, j))。显然，我们事实上可以不用保存具体的字符串（因为有最后一个字符串就够用了），而且可以事先计算出每两个字符串之间的overlap（这样就不需要重复计算）。不过这样就需要最后重建DP过程了……不过字符串处理过程太耗时了，也可以理解……
不过这样做了之后时间效率大大提高了（从1324ms提高到了28ms）
https://zxi.mytechroad.com/blog/searching/leetcode-943-find-the-shortest-superstring/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)
string shortestSuperstring(vector<string>& A) {
const int n = A.size();
g_ = vector<vector<int>>(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<int> path(n);
best_len_ = INT_MAX;
dfs(A, 0, 0, 0, path);
string ans = A[best_path_[0]];
for (int k = 1; k < best_path_.size(); ++k) {
int i = best_path_[k - 1];
int j = best_path_[k];
ans += A[j].substr(A[j].length() - g_[i][j]);
}
return ans;
}
private:
vector<vector<int>> g_;
vector<int> best_path_;
int best_len_;
void dfs(const vector<string>& A, int d, int used, int cur_len, vector<int>& path) {
if (cur_len >= best_len_) return;
if (d == A.size()) {
best_len_ = cur_len;
best_path_ = path;
return;
}
for (int i = 0; i < A.size(); ++i) {
if (used & (1 << i)) continue;
path[d] = i;
dfs(A,
d + 1,
used | (1 << i),
d == 0 ? A[i].length() : cur_len + g_[path[d - 1]][i],
path);
}
}
https://www.geeksforgeeks.org/shortest-superstring-problem/
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.
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 verse. The maximum overlap mean length of the matching prefix and suffix is maximum.
