BFS Solution with explanation
The problem is just a slight modification of the Find Shortest Path Visiting All Nodes problem. \nBelow are some thoughts that led me to that solution:\n Findin
The problem is just a slight modification of the [Find Shortest Path Visiting All Nodes](https://leetcode.com/problems/shortest-path-visiting-all-nodes/) problem. \nBelow are some thoughts that led me to that solution:\n* Finding the worst, but correct, superstring is easy, just concatenate all the strings. \n* Let\'s assume we have just two strings **a** and **b**. What is the shortest superstring containing both of them? It depends on the order in which the strings should be merged. Let\'s call **c_ab** the suffix of **a** which is also a prefix of **b**, and **c_ba** on the contrary the suffix of **b** which is also a prefix of **a**. If **c_ab** is shorter than **c_ba** then the shortest superstring of **a** and **b** is **a+(b - c_ab)**, else it is **b+(a-c_ba)**.\n* The problem is in general about the right order of merging all the strings, so that the total superstring is shortest possible. That idea sounds much like the problem I provided link to above. The only thing left is to define weight, which is straightforward. Referring to the idea above the weight going from string **a** to string **b** would be length of **(b - c_ab)** and so on.\n\n\n```\nclass Solution {\n    public String shortestSuperstring(String[] A) {\n        if(A == null || A.length == 0) return "";\n        \n        int weights[][] = new int[A.length][A.length];\n        \n        for(int i = 0;i<A.length;i++) {\n            for(int j = i+1;j<A.length;j++) {\n                weights[i][j] = getWeight(A[i], A[j]);\n                weights[j][i] = getWeight(A[j], A[i]);\n            }\n        }\n        \n        return concatSmart(A, weights);\n    }\n    \n    String concatSmart(String [] A, int [][] weights) {\n        \n        int memo[][] = new int[A.length][1<<A.length];\n        \n        Queue<Pair> bfs = new PriorityQueue<>(new Comparator<Pair>() {\n            @Override\n            public int compare(Pair a, Pair b) {\n                return Integer.compare(a.weight, b.weight);\n            }\n        });\n        \n        for(int [] row:memo) Arrays.fill(row, Integer.MAX_VALUE);\n        \n        for(int i = 0;i<A.length;i++) {\n            bfs.add(new Pair(A[i], i, A[i].length(), 1<<i));\n            memo[i][1<<i] = A[i].length();\n        }\n        \n        while(!bfs.isEmpty()) {\n            Pair node = bfs.poll();\n            \n            if(node.mask == memo[node.index].length-1) return node.str;\n            \n            for(int i = 0;i<A.length;i++) {\n                int newMask = node.mask | (1<<i);\n                if(newMask != node.mask && memo[i][newMask] > memo[node.index][node.mask]+weights[node.index][i]) {\n                    bfs.add(new Pair(concat(node.str, A[i], weights[node.index][i]), i, node.weight+weights[node.index][i], newMask));\n                    memo[i][newMask] = node.weight+weights[node.index][i];\n                }\n            }\n        }\n        \n        throw null;\n    }\n    \n   \n    \n    String concat(String a, String b, int commonPartLength) {\n        return a + b.substring(b.length()-commonPartLength, b.length());\n    }\n    \n    int getWeight(String a, String b) {\n        String kmpStr = b+"#"+a;\n        int kmp [] = new int[kmpStr.length()];\n        \n        int k = 1;\n        for(int i = 1;i<kmpStr.length();i++) {\n            int j = kmp[i-1]; \n            while(j != 0 && kmpStr.charAt(i) != kmpStr.charAt(j)) {\n                j = kmp[j-1];\n            }\n            if(kmpStr.charAt(i) == kmpStr.charAt(j)) {\n                ++j;\n            }\n            kmp[i] = j;\n        }\n        \n        int x = kmp[kmp.length-1];\n        \n        return b.length() - x;\n    }\n    \n    String join(String [] A) {\n        StringBuilder res = new StringBuilder();\n        for(String str:A) res.append(str);\n        return res.toString();\n    }  \n    \n    class Pair {\n        String str;\n        int index;\n        int weight;\n        int mask;\n        \n        public Pair(String str, int index, int weight, int mask) {\n            this.str = str;\n            this.index = index;\n            this.weight = weight;\n            this.mask = mask;\n        }\n    }\n}\n```
[]