[Leetcode] Problem 943 - Find the Shortest Superstring

Posted on | In ,

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

No.1

Input: [“alex”,”loves”,”leetcode”]

Output: “alexlovesleetcode”

Explanation: All permutations of “alex”,”loves”,”leetcode” would also be accepted.

No.2

Input: [“catg”,”ctaagt”,”gcta”,”ttca”,”atgcatc”]

Output: “gctaagttcatgcatc”

Note

  1. 1 <= A.length <= 12
  2. 1 <= A[i].length <= 20

Code

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// cost[i][j]: the cost of appending A[j] after A[i]
// dp[s][i] = min{d[s - 2^i][j] + cost[j][i]}: min cost to visit nodes of s and ends with i
// dp[2^i][i] = A[i].length
// min = min{dp[2^n - 1][*]}
public String shortestSuperstring(String[] A) {
    StringBuilder sb = new StringBuilder();
    int n = A.length;
    int[][] cost = new int[n][n];
    int[][] dp = new int[1 << n][n];
    int[][] parent = new int[1 << n][n];
    int min = Integer.MAX_VALUE;
    int node = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cost[i][j] = getCost(A[i], A[j]);
            cost[j][i] = getCost(A[j], A[i]);
        }
    }

    for (int i = 0; i < (1 << n); i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
        Arrays.fill(parent[i], -1);
    }
    for (int i = 0; i < n; i++) 
        dp[1 << i][i] = A[i].length();

    for (int s = 0; s < (1 << n); s++) {
        for (int i = 0; i < n; i++) {
            if ((s & (1 << i)) == 0)
                continue;
            
            int preState = s & ~ (1 << i);
            
            for (int j = 0; j < n; j++) {
                if (dp[preState][j] + cost[j][i] < dp[s][i]) {
                    dp[s][i] = dp[preState][j] + cost[j][i];
                    parent[s][i] = j;
                }
            }

            if (s == (1 << n) - 1 && dp[s][i] < min) {
                min = dp[s][i];
                node = i;
            }
        }
    }

    int curState = (1 << n) - 1;

    while (curState != 0) {
        int preNode = parent[curState][node];

        if (preNode >= 0)
            sb.insert(0, A[node].substring(A[node].length() - cost[preNode][node]));
        else 
            sb.insert(0, A[node]);

        curState &= ~ (1 << node);
        node = preNode;
    }

    return sb.toString();
}

private int getCost(String a, String b) {
    int cost = b.length();
    int len = Math.min(a.length(), b.length());

    for (int i = 1; i <= len; i++) {
        if (b.startsWith(a.substring(a.length() - i)))
            cost = b.length() - i;
    }

    return cost;
}