943. Find the Shortest Superstring

Version #1 DP

非常难的一道题
bug出在了当A[i] 为第一个word的时候，如果不设parent[1 << i][i] = i 而default为0的话就会陷入死循环
其余的思路其实和knapsack有点类似
关键在于状态压缩
把两个word之间的连接状态，压缩成一个已知的set，append一个word的状态

95.59 %
class Solution {
    public String shortestSuperstring(String[] A) {
        // int state -> which words index have been visited
        // dp[state][i] -> minimum superstring length to cover state, and i is the last word
        // having dp[state][j] -> try to expand to word that have not been visited before
        // dp[state][i] = Math.min(dp[state][i], dp[state][j] + cost[j][i])
        // store the last index j for dp[state][i] -> parent[state][i] = j
        // cost[i][j] -> the length increased to append A[j] after A[i], not including length of A[i]
        int len = A.length;
        int[][] cost = new int[len][len];
        int endState = 0; // if state reached this state, we know that all words have been used
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                cost[i][j] = getCost(A[i], A[j]);
                cost[j][i] = getCost(A[j], A[i]);
            }
            endState += 1 << i;
        }
        int totalCost = Integer.MAX_VALUE;
        int lastIndex = 0;
        int[][] dp = new int[endState + 1][len];
        int[][] parent = new int[endState + 1][len]; // parent index for min cost
        for (int i = 0; i < len; i++) {
            dp[1 << i][i] = A[i].length(); // A[i] is the first word, cost is it self
            parent[1 << i][i] = i;
        }
        for (int s = 0; s <= endState; s++) {
            for (int i = 0; i < len; i++) {
                // check if this state has visited A[i] or not
                if ((s & (1 << i)) == 0 || s == (1 << i)) continue;
                dp[s][i] = Integer.MAX_VALUE;
                int prevState = s & (~(1 << i)); // reset bit i
                for (int j = 0; j < len; j++) {
                    if ((prevState & (1 << j)) == 0) continue;
                    // All possible prev states
                    if (dp[prevState][j] + cost[j][i] < dp[s][i]) {
                        dp[s][i] = dp[prevState][j] + cost[j][i];
                        parent[s][i] = j;
                    }
                }
                if (s == endState && dp[s][i] < totalCost) {
                    totalCost = dp[s][i];
                    lastIndex = i;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (endState != 0) {
            int curr = lastIndex;
            lastIndex = parent[endState][curr];
            endState = endState & (~(1 << curr)); // reset lastIndex
            String temp = A[curr].substring(A[curr].length() - cost[lastIndex][curr]);
            sb.insert(0, temp);
        }
        sb.insert(0, A[lastIndex]);
        return sb.toString();
    }
   
    private int getCost(String first, String second) {
        // abcd     cdef
        int overlap = 0;
        for (int i = 0; i < first.length(); i++) {
            if (second.startsWith(first.substring(i))) {
                overlap = first.length() - i;
                break;
            }
        }
        return second.length() - overlap;
    }
}