Java | Held Karp (TSP) | Concise w/ explanations!
Foreword\nI think this problem is a bit hard because there was a bug in my code that took me hours to catch.\nIt was a silly bug but it does test you on whether
#### Foreword\nI think this problem is a bit hard because there was a bug in my code that took me hours to catch.\nIt was a silly bug but it does test you on whether you really understand the Held Karp DP to solve TSP.\nMy suffering has just ended! \n\nIt is hard to imagine this question only got a rating of 21xx on https://zerotrac.github.io/leetcode_problem_rating/#/\n\n#### Details\n- Here `discount[i][j]` means how many letters we save if we go from `words[i]` to `words[j]`, so "abccd" to "ccdxx" would be 3, while "ccdxx" to "abccd" would be 0.\n\n- DP is just the standard Held Karp DP. Nothing unusual here, but we also need to save the path, and we will need a 2D array for it, with the 1st dimension being the next mask, and the second dimension being the next city. That way, we will be able to look up previous city since we know that it ends at `0b111...111`  mask. We also know the city that it ends at city `j` when `dp[0b111...111][j]` is the greatest element among all `dp[0b111...111]` subarray.\n\n- When building the path, we can use `stringbuilder.insert(0, word)` but it is ineffecient. We can instead just use a String array and call `String.join()` at the end.\n\n#### End\nThat\'s it. I hope it help someone!\n\n#### Time Complexity: O(2^n * n^2)\n#### Space Complexity: (2^n * n + n^2)\n```Java\nclass Solution {\n    public String shortestSuperstring(String[] words) {\n        int n = words.length;\n        int[][] discount = new int[n][n];\n        for (int i = 0; i < n; i++){\n            for (int j = 0; j < n; j++){\n                for (int k = 0; k < words[i].length()&&i!=j; k++){ // build discount map from i->j and j->i\n                    if (words[j].startsWith(words[i].substring(k))){\n                        discount[i][j]=words[i].length()-k;\n                        break;\n                    }\n                }\n            }\n        }\n        int[][] dp = new int[1<<n][n];\n        int[][] path = new int[1<<n][n];\n        for (int i = 0; i < 1<<n; i++){ // find the max discount for mask (1<<n)-1 with dp\n            for (int j = 0; j < n; j++){\n                for (int k = 0; k < n && (i&1<<j)>0; k++){\n                    if ((i&1<<k)==0 && dp[i][j]+discount[j][k]>=dp[i|1<<k][k]){\n                        dp[i|1<<k][k]=dp[i][j]+discount[j][k];\n                        path[i|1<<k][k]=j;\n                    }\n                }\n            }\n        }\n        int m = (1<<n)-1, idx = n; // build the path from end to start\n        int end=IntStream.range(0,n).reduce((a,b)->dp[(1<<n)-1][a]>dp[(1<<n)-1][b]?a:b).getAsInt();\n        String[] ans = new String[n];\n        while(m>0){\n            ans[--idx]=words[end].substring((m&(m-1))==0?0:discount[path[m][end]][end]);\n            m^=1<<end;\n            end=path[m|1<<end][end];\n        }\n        return String.join("",ans);\n    }\n}\n```
['Dynamic Programming', 'Java']