Travelling Salesman Problem
Travelling Salesman Problem\n\n1. graph[i][j] means the length of string to append when A[i] followed by A[j]. eg. A[i] = abcd, A[j] = bcde, then graph[i][j] = 
[Travelling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem)\n\n1. `graph[i][j]` means the length of string to append when `A[i]` followed by `A[j]`. eg. `A[i] = abcd`, `A[j] = bcde`, then `graph[i][j] = 1`\n2. Then the problem becomes to: find the shortest path in this graph which visits every node exactly once. This is a Travelling Salesman Problem.\n3. Apply TSP DP solution. Remember to record the path.\n\nTime complexity: `O(n^2 * 2^n)`\n\n```\nclass Solution {\n    public String shortestSuperstring(String[] A) {\n        int n = A.length;\n        int[][] graph = new int[n][n];\n        // build the graph\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                graph[i][j] = calc(A[i], A[j]);\n                graph[j][i] = calc(A[j], A[i]);\n            }\n        }\n        int[][] dp = new int[1 << n][n];\n        int[][] path = new int[1 << n][n];\n        int last = -1, min = Integer.MAX_VALUE;\n\t\t\n        // start TSP DP\n        for (int i = 1; i < (1 << n); i++) {\n            Arrays.fill(dp[i], Integer.MAX_VALUE);\n            for (int j = 0; j < n; j++) {\n                if ((i & (1 << j)) > 0) {\n                    int prev = i - (1 << j);\n                    if (prev == 0) {\n                        dp[i][j] = A[j].length();\n                    } else {\n                        for (int k = 0; k < n; k++) {\n                            if (dp[prev][k] < Integer.MAX_VALUE && dp[prev][k] + graph[k][j] < dp[i][j]) {\n                                dp[i][j] = dp[prev][k] + graph[k][j];\n                                path[i][j] = k;\n                            }\n                        }\n                    }\n                }\n                if (i == (1 << n) - 1 && dp[i][j] < min) {\n                    min = dp[i][j];\n                    last = j;\n                }\n            }\n        }\n\t\t\n        // build the path\n        StringBuilder sb = new StringBuilder();\n        int cur = (1 << n) - 1;\n        Stack<Integer> stack = new Stack<>();\n        while (cur > 0) {\n            stack.push(last);\n            int temp = cur;\n            cur -= (1 << last);\n            last = path[temp][last];\n        }\n\t\t\n        // build the result\n        int i = stack.pop();\n        sb.append(A[i]);\n        while (!stack.isEmpty()) {\n            int j = stack.pop();\n            sb.append(A[j].substring(A[j].length() - graph[i][j]));\n            i = j;\n        }\n        return sb.toString();\n    }\n    private int calc(String a, String b) {\n        for (int i = 1; i < a.length(); i++) {\n            if (b.startsWith(a.substring(i))) {\n                return b.length() - a.length() + i;\n            }\n        }\n        return b.length();\n    }\n}\n```
[]