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();
    }
}

All Problems

All Solutions