943. Find the Shortest Superstring

class Solution {
    public String shortestSuperstring(String[] words) {
        int n = words.length;
        int[][] graph = new int[n][n];
        buildGraph(graph, words);
        
        int[][] dp = new int[1 << n][n];
        int[][] path = new int[1 << n][n];
        int min = Integer.MAX_VALUE;
        int last = -1;
        for (int i = 0; i < path.length; i++) {
            Arrays.fill(path[i], -1);
        }
        
        for (int curState = 1; curState < (1 << n); curState++) {
            Arrays.fill(dp[curState], Integer.MAX_VALUE / 2);
            
            for (int curNode = 0; curNode < n; curNode++) {
                if ((curState & (1 << curNode)) == 0) continue;
                int prevState = curState ^ (1 << curNode);
                if (prevState == 0) {
                    dp[curState][curNode] = words[curNode].length();
                } else {
                    for (int prevNode = 0; prevNode < n; prevNode++) {
                        if (dp[prevState][prevNode] + graph[prevNode][curNode] < 
                            dp[curState][curNode]) {
                            dp[curState][curNode] = dp[prevState][prevNode] + graph[prevNode][curNode];
                            path[curState][curNode] = prevNode;
                        }
                    }
                }
                
                if (curState == (1 << n) - 1 && dp[curState][curNode] < min) {
                    min = dp[curState][curNode];
                    last = curNode;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int s = (1 << n) - 1;
        while (s > 0) {
            int prevNode = path[s][last];
            if (prevNode == -1) {
                sb.insert(0, words[last]);
            } else {
                sb.insert(0, words[last].substring(words[last].length() - graph[prevNode][last]));
            }
            
            s = s ^ (1 << last);
            last = prevNode;
        }
        
        return sb.toString();
    }
    
    private void buildGraph(int[][] graph, String[] words) {
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                boolean found = false;
                for (int index = 0; index < words[i].length(); index++) {
                    if (words[j].startsWith(words[i].substring(index))) {
                        graph[i][j] = words[j].length() - (words[i].length() - index);
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    graph[i][j] = words[j].length();
                }
            }
        }
    }
}