BFS + PriorityQueue is all you need
If you cannot understand this method, look at lc 847 and lc 743\nlc 847 will tell you what the state means in this problem\nlc 743 will tell you how to use Prio
If you cannot understand this method, look at lc 847 and lc 743\nlc 847 will tell you what the state means in this problem\nlc 743 will tell you how to use PriorityQueue to find shortest path in graph with weights\n\n"We may assume that no string in A is substring of another string in A" \nWhich means in Path A-B-C-D\uFF0Cthe dependence of D to C\uFF0Cis independent of A,B,C\nSo the cost to add D behind C, is the same as the cost of adding D to shortestSuperstring(ABC)\nWe build the graph according to this clue\n\nThe problem can be transformed into:\n1. Starting from each single node in A, visit the other nodes in A for one time, calculate the total cost.\n   By Dijkstra, we know using a PriorityQueue can lead to the shortest path start from this single node.\n2. Find the min cost in N total costs in step 1.\n\nT:O(N*2^N)\nS:O(N*2^N)\n\n```\nclass Solution {\n    \n    class State{\n        int node;  //current node index\n        int state;  //distinguish the node come from diferent node\n        StringBuilder sb; //the accumulated string in this state\n        int cost;  //the accumulated cost\n\n        public State(int node, int state, String str, int cost){\n            this.node = node;\n            this.state = state;\n            this.sb = new StringBuilder(str);\n            this.cost = cost;\n        }        \n        \n    }\n    \n    public String shortestSuperstring(String[] A) {\n        int n = A.length;\n        int goal = (1<<n) - 1;\n        \n        List<String> waitlist = new ArrayList<>();  //store the min cost start from each single node\n        \n        Map< Integer, List<List<Integer>> > map = new HashMap<>();  //<s1 index, <<s2 index, cost>,<s3 index, cost>...> >\n        \n        for(int i=0; i<A.length; i++) map.put(i, new ArrayList<>());\n\n        //build the graph\n        for(int i=0; i<A.length; i++){\n            for(int j=0; j<A.length; j++){\n                if(A[i].equals(A[j])) continue;\n                List<Integer> temp = new ArrayList<>();\n                temp.add(j);\n                temp.add(calcost(A[i], A[j]));\n                \n                map.get(i).add( new ArrayList<>(temp) ) ;\n            }\n        }\n\n        \n        Comparator<State> mycomp = new Comparator<>(){\n            public int compare(State s1, State s2){\n                return s1.cost - s2.cost;\n            }\n        };\n        \n        // for each node, we do bfs\n        for(int i=0; i<A.length; i++){\n            Queue<State> pq =  new PriorityQueue<>(mycomp);\n            boolean [][]visited = new boolean [n][1<<n];\n            pq.add(new State(i, 1<<i, A[i], 0));\n            visited[i][1<<i] = true;\n            \n            while(!pq.isEmpty()){\n                State currstate = pq.poll();\n                if(currstate.state == goal) waitlist.add(currstate.sb.toString());\n                \n                for(List<Integer> nextnodelist : map.get(currstate.node)){\n                    int nextnode = nextnodelist.get(0);\n                    int nextcost = nextnodelist.get(1);\n                    int nextstate = currstate.state | (1<<nextnode);\n                    \n                    if(visited[nextnode][nextstate]) continue; \n            \n                    visited[nextnode][nextstate] = true;\n                     \n                    //do not modify currstate.sb\n                    StringBuilder nextsb = new StringBuilder(currstate.sb.toString());\n                    //"abcd" + "bcde", nextcost is 1, we only need to add "e" behind \n                    nextsb.append( A[nextnode].substring(A[nextnode].length()-nextcost) );  \n                    \n                    pq.add(new State(nextnode, nextstate, nextsb.toString(), currstate.cost+nextcost));\n                }\n            }\n\n        }\n        \n        int minlen = Integer.MAX_VALUE;\n        String minstr = "";\n\n        for(String str : waitlist){\n            if(minlen > str.length()){\n                minlen = str.length();\n                minstr = str;\n            }\n        }\n        \n        return minstr;\n    }\n    \n    //original "abcd" add an extra "bcde", result is "abcde", so the cost is 1\n    //use KMP can spped up this process, here I use an intuitive method\n    public int calcost(String s1, String s2){\n        int len1 = s1.length(), len2 = s2.length();\n        int minlen = Math.min(len1, len2);\n        int commonlen = 0;\n        int maxcommonlen = 0;\n    \n        // s1[i, len1) match s2[0, j)\n        while(commonlen < minlen){\n            int i = len1 - 1 - commonlen;\n            int j = commonlen + 1;\n            \n            //use commonlen to scan s1 and s2\n            if( s1.substring(i).equals(s2.substring(0,j)) ) {\n                maxcommonlen = commonlen + 1;\n            }\n            \n            commonlen++;\n        }\n        return len2 - maxcommonlen;\n    }\n}\n```\n\nIf you find this helpful, please vote up so that more people can see.
['Breadth-First Search', 'Java']