Problem
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 <= 12
1 <= A[i].length <= 20
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)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// Author: Huahua, running time: 692 ms class Solution { public: 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); } } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// Author: Huahua, 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)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
// Author: Huahua, 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; } }; |