LeetCode 943 "Find the Shortest Superstring", Java version

943.java

class Solution {
    String[] words;
    int n;
    int[][] prefix; // prefix[i][j] is the minimal k such that words[i][k:] is a prefix of words[j]
    int[][] answer; // answer[first][ban]

    public String shortestSuperstring(String[] words) {
        init(words);

        int first = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int v = search(i, 0);
            if (min > v) {
                min = v;
                first = i;
            }
        }

        int[] seq = reconstruct(first);
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i == n-1) {
                s.append(words[seq[i]]);
            } else {
                s.append(words[seq[i]].substring(0, prefix[seq[i]][seq[i+1]]));
            }
        }

        return s.toString();
    }

    void init(String[] s) {
        words = s;
        n = words.length;

        prefix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                for (int k = 0; k <= words[i].length(); k++) {
                    if (words[j].startsWith(words[i].substring(k))) {
                        prefix[i][j] = k;
                        break;
                    }
                }
            }
        }

        answer = new int[n][1 << n];
    }

    // Ban set manipulation
    static boolean has(int ban, int i) { return (ban & (1 << i)) != 0; }
    static int with(int ban, int i) { return ban | (1 << i); }

    int search(int first, int ban) {
        if (answer[first][ban] != 0) {
            return answer[first][ban];
        }
        int newban = with(ban, first); // Ban the first now that we're using it
        if (newban == (1 << n) - 1) {
            // No other words to use
            int v = words[first].length();
            answer[first][ban] = v;
            return v;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (has(newban, i)) {
                continue;
            }
            int v = prefix[first][i] + search(i, newban);
            min = Math.min(min, v);
        }
        answer[first][ban] = min;
        return min;
    }

    int[] reconstruct(int first) {
        int[] seq = new int[n];
        seq[0] = first;
        int prev = first;
        int prevban = 0;
        for (int d = 1; d < n; d++) {
            // The following mirrors the search method above
            int ban = with(prevban, prev);
            for (int i = 0; i < n; i++) {
                if (has(ban, i)) {
                    continue;
                }
                if (answer[prev][prevban] == prefix[prev][i] + answer[i][ban]) {
                    seq[d] = i;
                    prev = i;
                    prevban = ban;
                }
            }
        }
        return seq;
    }
}