Java Graph, TSP and DP
1, build a directed graph, where edge values are cost to concate from string to next string;\n2, find 1 route from the graph to\na, include all nodes once and o
1, build a directed graph, where edge values are cost to concate from string to next string;\n2, find 1 route from the graph to\na, include all nodes once and only once;\nb, make sure the cost are the minmum;\n\nFrom the above 2, it is the defination similar to TSP (Travelling Salesman Problem);\nRef https://leetcode.com/problems/find-the-shortest-superstring/discuss/194932/Travelling-Salesman-Problem\n\n```\nclass Solution {\n    public String shortestSuperstring(String[] A) {\n        int n = A.length, path[][] = new int[1 << n][n], g[][] = buildGraph(A), min = Integer.MAX_VALUE, last = 0;\n        Integer[][] dp = new Integer[1 << n][n];\n        for (int i = 1; i < dp.length; i++) {\n            for (int j = 0; j < n; j++) {\n                if ((i & (1 << j)) == 0) continue;\n                int prev = i - (1 << j);\n                if (prev == 0) {\n                    dp[i][j] = A[j].length();\n                    continue;\n                }\n                dp[i][j] = Integer.MAX_VALUE;\n                for (int k = 0; k < n; k++) {\n                    if (dp[prev][k] != null && dp[i][j] > dp[prev][k] + g[k][j]){\n                        dp[i][j] = dp[prev][k] + g[k][j];\n                        path[prev][j] = k;  // could also be [prev][i], but not saving space;\n                    }\n                }\n                if (i == (1 << n) - 1 && dp[i][j] != null && dp[i][j] < min) {\n                    min = dp[i][j];\n                    last = j;\n                }\n            }\n        }\n\n        List<Integer> route = new ArrayList<>();\n        int curr = (1 << n) - 1;\n        while (curr > 0) {\n            route.add(last);\n            curr -= (1 << last);\n            last = path[curr][last];\n        }\n        StringBuilder sb = new StringBuilder();\n        sb.append(A[route.get(route.size() - 1)]);\n        for (int i = route.size() - 2; i >= 0; i--) {\n            sb.append(A[route.get(i)].substring(A[route.get(i)].length() - g[route.get(i + 1)][route.get(i)]));\n        }\n        return sb.toString();\n    }\n    \n    private int[][] buildGraph(String[] A) {\n        int n = A.length, g[][] = new int[n][n];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                g[i][j] = cost(A[i], A[j]);\n                g[j][i] = cost(A[j], A[i]);\n            }\n        }\n        return g;\n    }\n    \n    private int cost(String a, String b) {\n        int n = b.length(), m = a.length(), res = n;\n        for (int i = Math.min(m, n); i > 0; i--) {\n            boolean same = true;\n            for (int j = 0; j < i; j++) {\n                if (a.charAt(m - i + j) != b.charAt(j)) {\n                    same = false;\n                    break;\n                }\n            }\n            if (same) return n - i;\n        }\n        return n;\n    }\n}\n```
[]