Shortest Hamiltonian Path in weighted digraph (with instructional explanation)
1. Formulate the problem as a graph problem\nLet\'s consider each string as a node on the graph, using their overlapping range as a similarity measure, then the
***1. Formulate the problem as a graph problem***\nLet\'s consider each string as a node on the graph, using their overlapping range as a similarity measure, then the edge from string A to string B is defined as:\n```\n(A,B) = len(A) - overlapping(tail of A to head of B), \neg    A="catg" B= "atgcatc", overlapping is "atg",which is a tail part of A, and a head part of B, therefore (A,B) = 4-3 = 1\n```\nNotice here that we must formulate the problem setup as a digraph, as (A,B)!=(B,A)\neg   B="atgcatc" A="catg", overlapping is "c", so (B,A) = 7-1=6\n\nThus we can compute a distance matrix for this graph (see code below). Notice that the diagonal is always 0, and as this is a digraph, this matrix is asymmetric.\n\n***2. Using DP to find a minimum Hamiltonian cycle (which is in fact a Travelling Salesman Problem)***\nThe major steps here are:\n(1) We arbitrarily select a starting node. It doesn\'t matter which one we choose, as we are looking for a Hamiltonian cycle, so every node will be included and can be used as a starting node. Here we choose node 0.\n(2) We build a path by selecting a node as an endpoint, and build it up from there. For example,\n\n```\nWe want to compute a subpath containing {2,4,5}. We have 3 candidates here:\n2 as the endpoint, compute subproblem {4,5};\n4 as the endpoint, compute subproblem {2,5};\n5 as the endpoint, compute subprobelm {2,4};\nThe one with the minimum distance will be our choice.\n```\n\nNotice the base case here is simply a subpath of only one node i. In this case we simply return the distance from our starting node(0) to node i, this is where the pre-computed distance matrix comes in handy.\n`eg {i} = distance_matrix [0] [i]`\n\nAlso notice that I implement it as a top-down approach, a bottom up one is equally if not more efficient.\n\n***3. Convert the full tour to a path***\nWhy do we need to convert the tour to a path? This point can be subtle, as it seems that we can simply build the superstring directly from the tour, but there is a problem, our superstring might "wrap around" and fail to contain all the strings. Consider this example:\n\n```\n["catg","atgcatc"]\nThe distance matrix is\n0 1\n6 0\n```\n\nAnd the TSP algorithm will give the result of "catgcat", as the min distance is 7, and we indeed have 7 characters in the superstring, but do you see the problem here? "atgcatc" misses a "c"! This is because the "c" **wraps around** to the head of "catg". So the TSP algorithm give a correct result per se, but we need to modify it to get the correct Hamiltonian Path for our particular problem.\n\nBelow I will highlight the intuition, and the implementation favors clarity rather than efficiency.\n\nSay we\'ve found a tour, (0,2,4,3,1,0) for and input of 5 strings.\nNow there are 5 possible shortest Hamiltonian Paths as our candidates.\n`(0,2,4,3,1), (2,4,3,1,0), (4,3,1,0,2), (3,1,0,2,4), (1,0,2,4,3).`\nThe insight here is that **the length of these 5 paths may well be different**, precisely due to **the wrap around nature** of our string problem.\n\n```\nConsider this example:\n\n"catg","ttca"\n\nBoth "catgttca" and "ttcatg" will be valid Hamiltonian paths, as we only have 2 nodes here. So (1,2) and (2,1) are two valid paths.\nThe unmodified TSP might give us "catgtt" or "ttcatg", both of length 6. \n```\nNotice that for the first one, the "ca" of "ttca" wraps around to the head of "catg" as we explaned above, so "tcaa" is not actually contained in our result, but it\'s the correct tour! The second one is the one we want. **But depending our choice of starting node, we might get the first one.** That\'s why we need this extra step to convert a tour to a correct path.\nThis is, however, very straightforward, if not very efficient. We simply construct all the possible paths from the tour, and compare their length, then return the one with the min length. By this we solve the uncertainty with the starting point choice. In the original TSP, it doesn\'t matter where the salesman starts his journey, as it\'s a tour. But our superstring problem requires this small modification.\n\nBelow is the top down approach. For clarity and debugging purposes, I use a String to store the path. Arrays, tuples (if your language supports it) and any other data structure that preserves ordering will be adequate.\n\nAs I said, this is not the most efficient implementation of the TSP / Shortest Hamiltonian Path problem, but I hope this gives you an idea behind the algorithm and the subtleties of it when applied to another problem.\n\n```\nclass Solution {\n    int[][] distance;\n    Map<String,String> memo;\n    public String shortestSuperstring(String[] A) {\n        if(A.length==1) return A[0];\n        buildDistanceMatrix(A);\n        memo = new HashMap<>();\n        //build key for the final solution, key is in the form "end:set of nodes", eg "0:1,2,3,4"\n        StringBuilder builder = new StringBuilder();\n        for(int i=1; i<A.length; i++){\n            builder.append(i);\n            builder.append(",");\n        }\n        builder.deleteCharAt(builder.length() - 1);\n        String key = "0"+":"+builder.toString();\n        \n        // start top-down algo, val is in the form of "sequence;minDistance", eg "0,3,4,2,1,0;20"\n        String seq = TSP(key).split(";")[0];\n        String res = convertToHP(seq,A);\n        return res;\n    }\n    \n    private String convertToHP(String seq, String[]A){\n        String[] tour = seq.split(",");\n        int N = tour.length-1;\n        int[] hamPath = new int[N];\n        for(int i=0; i<N; i++){\n            hamPath[i] = Integer.parseInt(tour[i]);\n        }\n        \n        int[][] pool = new int[N][N];\n        pool[0] = hamPath;\n        for(int i=1; i<N; i++){\n            int[]candidate = new int[N];\n            for(int j=i; j<i+N; j++){\n                candidate[j-i] = hamPath[j%N];\n            }\n            pool[i] = candidate;\n        }\n        int min = 1000;\n        String sol = "";\n        for(int[]path:pool){\n            String res = buildPath(path,A);\n            if(res.length()<min){\n                min = res.length();\n                sol = res;\n            }\n        }\n        return sol;\n    }\n    \n    private String buildPath(int[]path,String[]A){\n        StringBuilder builder = new StringBuilder();\n        for(int j=0; j<path.length-1; j++){\n            int start = path[j];\n            int end = path[j+1];\n            int len = distance[start][end];\n            builder.append(A[start].substring(0,len));\n        }\n        builder.append(A[path[path.length-1]]);\n        return builder.toString();\n    }\n    \n    private void buildDistanceMatrix(String[]A){\n        int N = A.length;\n        distance = new int[N][N];\n        for(int i=0; i<N; i++){\n            for(int j=0; j<N; j++){\n                if(i==j) continue;\n                String start = A[i];\n                String end = A[j];\n                for(int k=Math.min(start.length(),end.length()); k>0; k--){\n                    if(start.endsWith(end.substring(0,k))){\n                        distance[i][j] = start.length()-k;\n                        break;\n                    }\n                    else distance[i][j] = start.length();\n                }\n            }\n        }\n    }\n    \n    private String TSP(String key){\n        if(memo.containsKey(key)) return memo.get(key);\n        \n        String[] temp = key.split(":");\n        String endPointS = temp[0];\n        int endPoint = Integer.parseInt(endPointS);\n        \n        //base case\n        if(key.endsWith(":")){\n            String seq = "0"+","+endPointS;\n            int dist = distance[0][endPoint];\n            String res = seq+";"+Integer.toString(dist);\n            memo.put(key,res);\n            return res;\n        }\n        \n        String[] elements = temp[1].split(",");\n        int min = 1000;\n        String candidate="X";\n        for(int i=0; i<elements.length; i++){\n            String subKey = buildKey(elements, i);\n            String[] res = TSP(subKey).split(";");\n            int updatedDist = distance[Integer.parseInt(elements[i])][endPoint] + Integer.parseInt(res[1]);\n            String updatedSeq = res[0] + "," + endPointS;\n            if(updatedDist<min){\n                min = updatedDist;\n                candidate = updatedSeq;\n            }\n        }\n        String val = candidate + ";" + Integer.toString(min);\n        memo.put(key,val);\n        return val;\n    }\n    \n    private String buildKey(String[]s, int excl){\n        String endPoint = s[excl];\n        StringBuilder builder = new StringBuilder();\n        builder.append(endPoint);\n        builder.append(":");\n        if(s.length==1) return builder.toString();\n        \n        for(String node:s){\n            if(node.equals(endPoint))continue;\n            builder.append(node);\n            builder.append(",");\n        }\n        builder.deleteCharAt(builder.length() - 1);\n        return builder.toString();\n    }\n}\n```
[]