Find the Shortest Superstring LeetCode solution in Java

1
class Solution {
2
  public String shortestSuperstring(String[] words) {
3
    int n = words.length;
4
    int[][] discount = new int[n][n];
5
    for (int i = 0; i < n; i++) {
6
      for (int j = 0; j < n; j++) {
7
        for (int k = 0;
8
            k < words[i].length() && i != j;
9
            k++) { // build discount map from i->j and j->i
10
          if (words[j].startsWith(words[i].substring(k))) {
11
            discount[i][j] = words[i].length() - k;
12
            break;
13
          }
14
        }
15
      }
16
    }
17
    int[][] dp = new int[1 << n][n];
18
    int[][] path = new int[1 << n][n];
19
    for (int i = 0; i < 1 << n; i++) { // find the max discount for mask (1<<n)-1 with dp
20
      for (int j = 0; j < n; j++) {
21
        for (int k = 0; k < n && (i & 1 << j) > 0; k++) {
22
          if ((i & 1 << k) == 0 && dp[i][j] + discount[j][k] >= dp[i | 1 << k][k]) {
23
            dp[i | 1 << k][k] = dp[i][j] + discount[j][k];
24
            path[i | 1 << k][k] = j;
25
          }
26
        }
27
      }
28
    }
29
    int m = (1 << n) - 1, idx = n; // build the path from end to start
30
    int end =
31
        IntStream.range(0, n)
32
            .reduce((a, b) -> dp[(1 << n) - 1][a] > dp[(1 << n) - 1][b] ? a : b)
33
            .getAsInt();
34
    String[] ans = new String[n];
35
    while (m > 0) {
36
      ans[--idx] = words[end].substring((m & (m - 1)) == 0 ? 0 : discount[path[m][end]][end]);
37
      m ^= 1 << end;
38
      end = path[m | 1 << end][end];
39
    }
40
    return String.join("", ans);
41
  }
42
}