Modularized Travelling Salesman Problem Solution
Learned from Travelling Salesman Problem\n\nclass Solution {\n    public String shortestSuperstring(String[] A) {\n        int n = A.length;\n        int[][] gr
Learned from [Travelling Salesman Problem](https://www.youtube.com/watch?v=cY4HiiFHO1o)\n```\nclass Solution {\n    public String shortestSuperstring(String[] A) {\n        int n = A.length;\n        int[][] graph = new int[n][n];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                graph[i][j] = calWordDistance(A[i], A[j]);\n            }\n        }\n        int[][] dp = new int[n][1 << n];\n        setUp(graph, dp, n, A);\n        solve(graph, dp, n);\n        int[] tour = findOptimalTour(graph, dp, n);\n        StringBuilder sb = new StringBuilder();\n        merage(sb, tour, graph, A);\n        return sb.toString();\n    }\n    \n    private void setUp(int[][] graph, int[][] dp, int n, String[] A) {\n        for (int start = 0; start < n; start++) {\n            dp[start][1 << start] = A[start].length();\n        }\n    }\n    \n    private void solve(int[][] graph, int[][] dp, int n) {\n        for (int r = 2; r <= n; r++) {\n            List<Integer> list = combination(r, n);\n            for (int subset : list) {\n                for (int next = 0; next < n; next++) {\n                    if (notIn(next, subset)) continue;\n                    int state = (1 << next) ^ subset;\n                    int minDist = Integer.MAX_VALUE;\n                    for (int end = 0; end < n; end++) {\n                        if (end == next || notIn(end, subset)) continue;\n                        int newDist = dp[end][state] + graph[end][next];\n                        if (newDist < minDist) {\n                            minDist = newDist;\n                        }\n                    }\n                    dp[next][subset] = minDist;\n                }\n            }\n        }\n    }\n    \n    private int findMinCost(int[][] graph, int[][] dp, int n) {\n        int endState = (1 << n) - 1;\n        int minTourCost = Integer.MAX_VALUE;\n        for (int end = 0; end < n; end++) {\n            int tourCost = dp[end][endState];\n            if (tourCost < minTourCost) {\n                minTourCost = tourCost;\n            }\n        }\n        return minTourCost;\n    }\n    \n    private int[] findOptimalTour(int[][] graph, int[][] dp, int n) {\n        int endState = (1 << n) - 1;\n        int minTourCost = Integer.MAX_VALUE;\n        int lastIndex = -1;\n        for (int end = 0; end < n; end++) {\n            int tourCost = dp[end][endState];\n            if (tourCost < minTourCost) {\n                minTourCost = tourCost;\n                lastIndex = end;\n            }\n        }\n        int[] tour = new int[n];\n        tour[n - 1] = lastIndex;\n        int state = ((1 << n) - 1) ^ (1 << lastIndex);\n        for (int i = n - 2; i >= 0; i--) {\n            int index = -1;\n            for (int j = 0; j < n; j++) {\n                if (notIn(j, state)) continue;\n                if (index == -1) index = j;\n                int prevDist = dp[index][state] + graph[index][lastIndex];\n                int newDist = dp[j][state] + graph[j][lastIndex];\n                if (newDist < prevDist) {\n                    index = j;\n                }\n            }\n            tour[i] = index;\n            state = state ^ (1 << index);\n            lastIndex = index;\n        }\n        return tour;\n    }\n    \n    private List<Integer> combination(int r, int n) {\n        List<Integer> res = new ArrayList<>();\n        combination(res, r, n, 0, 0);\n        return res;\n    }\n    \n    private void combination(List<Integer> res, int r, int n, int pos, int temp) {\n        if (r == 0) {\n            res.add(temp);\n            return;\n        }\n        for (int i = pos; i < n; i++) {\n            temp = temp | (1 << i);\n            combination(res, r - 1, n, i + 1, temp);\n            temp = temp & ~(1 << i);\n        }\n    }\n    \n    private boolean notIn(int i, int subset) {\n        return (subset & (1 << i)) == 0;\n    }\n    private int calWordDistance(String a, String b) {\n        for (int i = 0; i < a.length(); i++) {\n            if (b.startsWith(a.substring(i))) {\n                return b.length() - (a.length() - i); //a == ga b == ab -> gab i == 1 dis = 2 - (2 - 1);\n            }\n        }\n        return b.length();\n    }\n\n    private void merage(StringBuilder sb, int[] tour, int[][] graph, String[] A) {\n        int lastIndex = -1;\n        for (int i : tour) {\n            if (lastIndex == -1) {\n                sb.append(A[i]);\n            } else {\n                int len = A[i].length();\n                int dis = graph[lastIndex][i];\n                sb.append(A[i].substring(len - dis));\n            }\n            lastIndex = i;\n        }\n    }\n}\n```
[]