A* search, python implementation 64ms pass
As the problem is almost as difficult as the traveling salesman problem, I think a good pruning method is necessary.\nTherefore, I tried the A search algorithms
As the problem is almost as difficult as the traveling salesman problem, I think a good pruning method is necessary.\nTherefore, I tried the A* search algorithms.\n\nHere is the idea:\n\n1. Imagine a graph. Each node is a sequence of a subset of words.\n2. Node *x* is connected to node *y* by appending one word *i* to *x*. The weight of the edge is the cost of appending the word *i*.\n3. The start is the emtpy sequence *[]*.\n4. The goal is the set of nodes that contains all words.\n5. Search the shortest path from start to goal.\n6. Based on the end node, we can construct the superstring according to the sequence.\n\nThe graph is huge. How do we search? Use A*.\n\n7. **Heuristics**: we can estimate the lower bound of the cost of each node to the goal by **summing up the minimum possible appending cost of all remaining words**.\n8. To be more specific, the minimum possible appending cost of a word is the number of extra letters of appending this word to any other word. This can be computed at first.\n\nHers is the solution implmented in python. It passes with 64 ms and is faster than 100.00% of other python solutions.\n\n```\nfrom heapq import heappush, heappop\n\ndef dist(v, w, eq):\n    if eq:\n        return 10000\n    else:\n        for i in xrange(1, len(w)):\n            if v.endswith(w[:-i]):\n                return i\n        return len(w)\n\ndef construct_seq(s, d, w):\n    t = w[s[0]]\n    for i in xrange(1, len(s)):\n        t = t + w[s[i]][-d[s[i-1]][s[i]]:]\n    return t\n\ndef heuristic(x, mdj):\n    return sum(mdj[i] for i in xrange(len(x)) if x[i] == 0)\n\ndef adjacent_nodes(x):\n    ret = []\n    for i in xrange(len(x)):\n        if x[i] == 0:\n            y = list(x)\n            y[i] = 1\n            ret.append((i, tuple(y)))\n    return ret\n    \nclass Solution(object):\n    def shortestSuperstring(self, A):\n        """\n        :type A: List[str]\n        :rtype: str\n        """\n        n = len(A)\n        \n        # special case\n        if n == 1:\n            return A[0]\n        # assert n > 1\n        \n        # distance between words\n        # dij := the cost in addition to add j after i\n        dij = [[dist(A[i], A[j], i == j) for j in xrange(n)] for i in xrange(n)]\n        \n        # minimum cost to add j\n        mdj = [min(dij[i][j] for i in xrange(n)) for j in xrange(n)]\n        \n        # A* search\n        # init\n        q = []          # priority queue with estimated cost\n        for i in xrange(n):\n            x = tuple(1 if j == i else 0 for j in xrange(n))\n            g = len(A[i])            # actual cost from start\n            h = heuristic(x, mdj)    # lower bound of cost till the goal\n            heappush(q, (g + h, g, h, x, [i]))\n            \n        best_f = None\n        best_p = None\n        while len(q) > 0:\n            # f, g, h, node, path\n            f, g, h, x, p = heappop(q)\n            \n            if best_f is not None and f >= best_f:\n                break\n                \n            for j, y in adjacent_nodes(x):\n                gy = g + dij[p[-1]][j]\n                py = p + [j]\n                \n                if sum(y) == n:     # is goal\n                    if best_f is None or gy < best_f:\n                        best_f = gy\n                        best_p = py\n                else:\n                    hy = heuristic(y, mdj)\n                    heappush(q, (gy + hy, gy, hy, y, py))\n                    \n        return construct_seq(best_p, dij, A)\n```\n\nI don\'t know exactly the complexity... Someone is interested in helping me?
[]