Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/943.html
943. Find the Shortest Superstring (Hard)
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
Related Topics:
Dynamic Programming
Solution 1. DP
// OJ: https://leetcode.com/problems/find-the-shortest-superstring/
// Time: O(N^2 * (2^N + W))
// Space: O(N * (2^N + W))
// Ref: https://leetcode.com/problems/find-the-shortest-superstring/solution/
class Solution {
public:
string shortestSuperstring(vector<string>& A) {
int N = A.size();
vector<vector<int>> overlaps(N, vector<int>(N));
for (int i = 0; i < N ; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) continue;
int len = min(A[i].size(), A[j].size());
for (int k = len; k >= 0; --k) {
if (A[i].substr(A[i].size() - k) != (A[j].substr(0, k))) continue;
overlaps[i][j] = k;
break;
}
}
}
vector<vector<int>> dp(1 << N, vector<int>(N));
vector<vector<int>> parent(1 << N, vector<int>(N, -1));
for (int mask = 0; mask < (1 << N); ++mask) {
for (int bit = 0; bit < N; ++bit) {
if (((mask >> bit) & 1) == 0) continue;
int pmask = mask ^ (1 << bit);
if (pmask == 0) continue;
for (int i = 0; i < N; ++i) {
if (((pmask >> i) & 1) == 0) continue;
int val = dp[pmask][i] + overlaps[i][bit];
if (val > dp[mask][bit]) {
dp[mask][bit] = val;
parent[mask][bit] = i;
}
}
}
}
vector<int> perm(N);
vector<bool> seen(N);
int t = 0, mask = (1 << N) - 1, p = 0;
for (int j = 0; j < N; ++j) {
if (dp[(1 << N) - 1][j] > dp[(1 << N) - 1][p]) p = j;
}
while (p != -1) {
perm[t++] = p;
seen[p] = true;
int p2 = parent[mask][p];
mask ^= 1 << p;
p = p2;
}
reverse(perm.begin(), perm.begin() + t);
for (int i = 0; i < N; ++i) {
if (!seen[i]) perm[t++] = i;
}
string ans = A[perm[0]];
for (int i = 1; i < N; ++i) {
int overlap = overlaps[perm[i - 1]][perm[i]];
ans += A[perm[i]].substr(overlap);
}
return ans;
}
};
-
class Solution { public String shortestSuperstring(String[] A) { int length = A.length; int[][] overlaps = new int[length][length]; for (int i = 0; i < length; i++) { for (int j = 0; j < length; j++) { if (i != j) { int strLength = Math.min(A[i].length(), A[j].length()); for (int k = strLength; k >= 0; k--) { if (A[i].endsWith(A[j].substring(0, k))) { overlaps[i][j] = k; break; } } } } } int states = 1 << length; int[][] dp = new int[states][length]; int[][] parents = new int[states][length]; for (int mask = 0; mask < states; mask++) { Arrays.fill(parents[mask], -1); for (int i = 0; i < length; i++) { if (((mask >> i) & 1) > 0) { int prevMask = mask ^ (1 << i); if (prevMask == 0) continue; for (int j = 0; j < length; j++) { if (((prevMask >> j) & 1) > 0) { int value = dp[prevMask][j] + overlaps[j][i]; if (value > dp[mask][i]) { dp[mask][i] = value; parents[mask][i] = j; } } } } } } int[] permutation = new int[length]; boolean[] visited = new boolean[length]; int permIndex = 0; int mask = states - 1; int strIndex = 0; for (int i = 0; i < length; i++) { if (dp[states - 1][i] > dp[states - 1][strIndex]) strIndex = i; } while (strIndex != -1) { permutation[permIndex++] = strIndex; visited[strIndex] = true; int parentIndex = parents[mask][strIndex]; mask ^= 1 << strIndex; strIndex = parentIndex; } for (int i = permIndex / 2 - 1; i >= 0; i--) { int temp = permutation[i]; permutation[i] = permutation[permIndex - 1 - i]; permutation[permIndex - 1 - i] = temp; } for (int i = 0; i < length; i++) { if (!visited[i]) permutation[permIndex++] = i; } StringBuffer sb = new StringBuffer(A[permutation[0]]); for (int i = 1; i < length; i++) { int overlap = overlaps[permutation[i - 1]][permutation[i]]; sb.append(A[permutation[i]].substring(overlap)); } return sb.toString(); } } ############ class Solution { public String shortestSuperstring(String[] words) { int n = words.length; int[][] g = new int[n][n]; for (int i = 0; i < n; ++i) { String a = words[i]; for (int j = 0; j < n; ++j) { String b = words[j]; if (i != j) { for (int k = Math.min(a.length(), b.length()); k > 0; --k) { if (a.substring(a.length() - k).equals(b.substring(0, k))) { g[i][j] = k; break; } } } } } int[][] dp = new int[1 << n][n]; int[][] p = new int[1 << n][n]; for (int i = 0; i < 1 << n; ++i) { Arrays.fill(p[i], -1); for (int j = 0; j < n; ++j) { if (((i >> j) & 1) == 1) { int pi = i ^ (1 << j); for (int k = 0; k < n; ++k) { if (((pi >> k) & 1) == 1) { int v = dp[pi][k] + g[k][j]; if (v > dp[i][j]) { dp[i][j] = v; p[i][j] = k; } } } } } } int j = 0; for (int i = 0; i < n; ++i) { if (dp[(1 << n) - 1][i] > dp[(1 << n) - 1][j]) { j = i; } } List<Integer> arr = new ArrayList<>(); arr.add(j); for (int i = (1 << n) - 1; p[i][j] != -1;) { int k = i; i ^= (1 << j); j = p[k][j]; arr.add(j); } Set<Integer> vis = new HashSet<>(arr); for (int i = 0; i < n; ++i) { if (!vis.contains(i)) { arr.add(i); } } Collections.reverse(arr); StringBuilder ans = new StringBuilder(words[arr.get(0)]); for (int i = 1; i < n; ++i) { int k = g[arr.get(i - 1)][arr.get(i)]; ans.append(words[arr.get(i)].substring(k)); } return ans.toString(); } } -
// OJ: https://leetcode.com/problems/find-the-shortest-superstring/ // Time: O(2^N * N * W) // Space: O(2^N * N * W) class Solution { public: string shortestSuperstring(vector<string>& A) { string dp[1 << 12] = {}; int overlap[12][12] = {}, last[1 << 12] = {}, N = A.size(); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) continue; int len = min(A[i].size(), A[j].size()) - 1; while (len >= 1 && A[i].substr(A[i].size() - len) != A[j].substr(0, len)) --len; overlap[i][j] = len; } } for (int mask = 0; mask < (1 << N); ++mask) { for (int i = 0; i < N; ++i) { if (mask >> i & 1) continue; int next = (mask | (1 << i)), len = mask ? overlap[last[mask]][i] : 0; auto s = dp[mask] + A[i].substr(len); if (dp[next].empty() || s.size() < dp[next].size()) { dp[next] = s; last[next] = i; } } } return dp[(1 << N) - 1]; } }; -
class Solution: def shortestSuperstring(self, words: List[str]) -> str: n = len(words) g = [[0] * n for _ in range(n)] for i, a in enumerate(words): for j, b in enumerate(words): if i != j: for k in range(min(len(a), len(b)), 0, -1): if a[-k:] == b[:k]: g[i][j] = k break dp = [[0] * n for _ in range(1 << n)] p = [[-1] * n for _ in range(1 << n)] for i in range(1 << n): for j in range(n): if (i >> j) & 1: pi = i ^ (1 << j) for k in range(n): if (pi >> k) & 1: v = dp[pi][k] + g[k][j] if v > dp[i][j]: dp[i][j] = v p[i][j] = k j = 0 for i in range(n): if dp[-1][i] > dp[-1][j]: j = i arr = [j] i = (1 << n) - 1 while p[i][j] != -1: i, j = i ^ (1 << j), p[i][j] arr.append(j) arr = arr[::-1] vis = set(arr) arr.extend([j for j in range(n) if j not in vis]) ans = [words[arr[0]]] + [words[j][g[i][j] :] for i, j in pairwise(arr)] return ''.join(ans) ############ # 943. Find the Shortest Superstring # https://leetcode.com/problems/find-the-shortest-superstring/ class Solution: def shortestSuperstring(self, words: List[str]) -> str: def distance(s1, s2): for i in range(1, len(s1)): if s2.startswith(s1[i:]): return len(s1) - i + 1 return 1 n = len(words) weights = [[0] * n for _ in range(n)] dp = [[0] * n for _ in range(1 << n)] queue = deque([(0, i, 1 << i, [i]) for i in range(n)]) full_mask = (1 << n) - 1 maxWeight, maxPath = -1, [] for i in range(n): for j in range(i, n): weights[i][j] = distance(words[i], words[j]) weights[j][i] = distance(words[j], words[i]) while queue: w, node, mask, path = queue.popleft() if dp[mask][node] != w: continue if mask == full_mask and w > maxWeight: maxWeight = w maxPath = path continue for nei in range(n): if mask & (1 << nei) > 0: continue new_mask = mask | (1 << nei) old = dp[new_mask][nei] new = dp[mask][node] + weights[node][nei] if new > old: dp[new_mask][nei] = new queue.append((new, nei, new_mask, path + [nei])) res = words[maxPath[0]] for i in range(1, n): prev, curr = maxPath[i - 1], maxPath[i] overlap = weights[prev][curr] - 1 res += words[curr][overlap:] return res -
func shortestSuperstring(words []string) string { n := len(words) g := make([][]int, n) for i, a := range words { g[i] = make([]int, n) for j, b := range words { if i != j { for k := min(len(a), len(b)); k > 0; k-- { if a[len(a)-k:] == b[:k] { g[i][j] = k break } } } } } dp := make([][]int, 1<<n) p := make([][]int, 1<<n) for i := 0; i < 1<<n; i++ { dp[i] = make([]int, n) p[i] = make([]int, n) for j := 0; j < n; j++ { p[i][j] = -1 if ((i >> j) & 1) == 1 { pi := i ^ (1 << j) for k := 0; k < n; k++ { if ((pi >> k) & 1) == 1 { v := dp[pi][k] + g[k][j] if v > dp[i][j] { dp[i][j] = v p[i][j] = k } } } } } } j := 0 for i := 0; i < n; i++ { if dp[(1<<n)-1][i] > dp[(1<<n)-1][j] { j = i } } arr := []int{j} vis := make([]bool, n) vis[j] = true for i := (1 << n) - 1; p[i][j] != -1; { k := i i ^= (1 << j) j = p[k][j] arr = append(arr, j) vis[j] = true } for i := 0; i < n; i++ { if !vis[i] { arr = append(arr, i) } } ans := &strings.Builder{} ans.WriteString(words[arr[n-1]]) for i := n - 2; i >= 0; i-- { k := g[arr[i+1]][arr[i]] ans.WriteString(words[arr[i]][k:]) } return ans.String() } func min(a, b int) int { if a < b { return a } return b }