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
- Method 1: search O(N! + N^2) AC 775ms
- First create a cost[i][j] matrix, means the number of characters need to be added at the end of the result if last added word is A[i] and we want to add A[j]. Cost matrix is calculated at the very beginning so it will be calculated once, and its time efficiency is O(n^2).
- We list all possible permutations and save the minimum. Pruning is required for remove useless iterations.
- We only record the path of words it goes through and concat the string at the end(we only concat once).
class Solution { public String shortestSuperstring(String[] A) { if(A.length == 1) return A[0]; int[][] cost = new int[A.length][A.length]; for(int i = 0; i < A.length; i++){ LABEL: for(int j = 0; j < A.length; j++){ if(i == j){ cost[i][j] = A[j].length(); }else{ int start = A[i].indexOf(A[j].charAt(0)); if(start == -1) cost[i][j] = A[j].length(); else{ for(int k = start; k < A[i].length(); k++){ if(A[j].startsWith(A[i].substring(k))){ cost[i][j] = A[j].length() - (A[i].length() - k); continue LABEL; } } cost[i][j] = A[j].length(); } } } } List<Integer> res = new ArrayList<>(); dfs(A, cost, 0, 0, new ArrayList<Integer>(), res, 0); StringBuilder sb = new StringBuilder(); for(int i = 0; i < res.size(); i++){ Integer path = res.get(i); sb.append(i == 0 ? A[path]: A[path].substring(A[path].length() - cost[res.get(i - 1)][path])); } return sb.toString(); } private int sum = Integer.MAX_VALUE; private void dfs(String[] A, int[][] cost, int index, int temp, List<Integer> path, List<Integer> res, int visited){ if(temp >= sum) return; if(A.length == index){ sum = temp; res.clear(); res.addAll(path); return; } for(int i = 0; i < A.length; i++){ if((visited & (1 << i)) > 0) continue; path.add(i); dfs(A, cost, index + 1, index == 0 ? A[i].length(): temp + cost[path.get(index - 1)][i], path, res, (visited | (1 << i))); path.remove(index); } } }
-
Method 1: brutal force
class Solution { public: string shortestSuperstring(vector<string>& A) { const int n = A.size(); g_ = vector<vector<int>>(n, vector<int>(n)); for(int f = 0; f < n; ++f){ int flen = A[f].length(); for(int s = 0; s < n; ++s){ if(s == f) continue; int slen = A[s].length(); g_[f][s] = slen; for(int i = 1; i <= min(flen, slen); ++i){ if(A[f].substr(flen - i) == A[s].substr(0, i)) g_[f][s] = slen - i; } } } vector<int> path(n); best_len_ = INT_MAX; dfs(A, 0, 0, 0, path); string res = A[path_[0]]; for(int i = 1; i < n; ++i){ int cur_len = A[path_[i]].length(); res += A[path_[i]].substr(cur_len - g_[path_[i - 1]][path_[i]]); } return res; } private: vector<vector<int>> g_; vector<int> path_; int best_len_; void dfs(const vector<string>& A, int d, int cur_len, int used, vector<int>& path){ if(cur_len >= best_len_) return; if(d == A.size()){ best_len_ = cur_len; path_ = path; return; } for(int i = 0; i < A.size(); ++i){ if(used & (1 << i)) continue; path[d] = i; dfs(A, d + 1, d == 0 ? A[i].length() : cur_len + g_[path[d - 1]][i], used | (1 << i), path); } } }; -
Method 2: DP
- dp[s][j]: s is a visited set in binary form, j is the output of current state.
- Transition function: dp[s][j] = min(dp[s - (1 << j)][i] + g[i][j])
- initialization: dp[1 << i][i] = A[i].length(), current string's length.
- final result: min(dp[2^n - 1][*]) with traceback.
class Solution { public: string shortestSuperstring(vector<string>& A) { const int n = A.size(); vector<vector<int>> g(n, vector<int>(n)); for(int f = 0; f < n; ++f){ int flen = A[f].length(); for(int s = 0; s < n; ++s){ if(s == f) continue; int slen = A[s].length(); g[f][s] = slen; for(int i = 1; i <= min(flen, slen); ++i){ if(A[f].substr(flen - i) == A[s].substr(0, i)) g[f][s] = slen - i; } } } vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX >> 1)); 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(!(ps & (1 << i))) continue; 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 res; while(s){ int i = parent[s][j]; if(i < 0) res = A[j] + res; else res = A[j].substr(A[j].length() - g[i][j]) + res; s &= ~(1 << j); j = i; } return res; } };