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. 1 <= A.length <= 12
  2. 1 <= 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;
    }
};

Java

  • 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();
        }
    }
    
  • // 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];
        }
    };
    
  • # 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
                
    
    

All Problems

All Solutions