python bfs solution with detailed explanation(with extra Chinese explanation)
you can get Chinese explanation here\n\nFirst, we convert this problem into a graph problem.\nfor instance, A = ["catg","ctaagt","gcta","ttca","atgcatc"]\nwe re
you can get Chinese explanation [here](https://buptwc.github.io/2018/11/19/Leetcode-943-Find-the-Shortest-Superstring/)\n\nFirst, we convert this problem into a graph problem.\nfor instance, `A = ["catg","ctaagt","gcta","ttca","atgcatc"]`\nwe regard each string in A as a node, and regard the repeat_length of two string as edge weight. then ,we get this graph `G`:\n![image](https://assets.leetcode.com/users/2017111303/image_1542604947.png)\n\nfor `G[2][1] = 3`, it means that we can `save` 3 characters length by place `node 1` behind `node 2`, etc `gctaagt`.\n\nIn the end, the more we `save`, the shorter string length we will get.\n\nSo, the question now is:\nIn a given graph, we can start in any node, and traverse all node in this graph excatly once, to get the maximum `save` length.\n(Note that although there is no connection between 1,3, you can still go from node 1 to node 3.)\n\nfirst we construct the graph:\n```python\ndef getDistance(s1, s2):\n        for i in range(1, len(s1)):\n            if s2.startswith(s1[i:]):\n                return len(s1) - i\n        return 0\n\nn = len(A)\nG = [[0]*n for _ in xrange(n)]\nfor i in range(n):\n    for j in range(i+1, n):\n        G[i][j] = getDistance(A[i], A[j])\n        G[j][i] = getDistance(A[j], A[i])\n```\n\nif we consider all possible case, it will be `n*(n-1)*(n-2)*...*1 = n!` possible cases. Obviously it won\u2019t work.\nWe need to make some optimizations, look at these two cases\uFF1A\n`2->1->3->...` and `1->2->3->...`\nBoth cases traverse three nodes 1, 2, and 3, and is currently at the `node 3`.\nfor `2->1->3->...`, we assume the `save length` now is `L1`\nfor `1->2->3->...`, we assume the `save length` now is `L2`\nif `L2 < L1`, regardless of how the strategy is adopted afterwards, the second case cannot be better than the first case. So we can discard the second case.\n\nBased on this idea, we difine `d[mask][node]` represent the now `save length` in the status `(mask, node)`.\n`mask` represent the node we have traversed, `10011` means traversed `node 0,1,4`\n`node` represent the current node.\n\nIn BFS solution, such a data structure is stored in the queue `(node, mask, path, s_len)`\n`path` means the order of traversed nodes.\n`s_len` means the `save length`.\n\nOnce `mask` == `(1<<n)-1`, it means that all nodes have been traversed. Now we find the maximum `s_len` and get the corresponding `path`.\nFinally, we construct the answer via `path`.\n\npython bfs code:\n```python\nclass Solution(object):\n    def shortestSuperstring(self, A):\n        def getDistance(s1, s2):\n            for i in range(1, len(s1)):\n                if s2.startswith(s1[i:]):\n                    return len(s1) - i\n            return 0\n\n        def pathtoStr(A, G, path):\n            res = A[path[0]]\n            for i in range(1, len(path)):\n                res += A[path[i]][G[path[i-1]][path[i]]:]\n            return res\n\n        n = len(A)\n        G = [[0]*n for _ in xrange(n)]\n        for i in range(n):\n            for j in range(i+1, n):\n                G[i][j] = getDistance(A[i], A[j])\n                G[j][i] = getDistance(A[j], A[i])\n\n        d = [[0]*n for _ in xrange(1<<n)]\n        Q = collections.deque([(i, 1<<i, [i], 0) for i in xrange(n)])\n        l = -1 # record the maximum s_len\n        P = [] # record the path corresponding to maximum s_len\n        while Q:\n            node, mask, path, dis = Q.popleft()\n            if dis < d[mask][node]: continue\n            if mask == (1<<n) - 1 and dis > l:\n                P,l = path,dis\n                continue\n            for i in xrange(n):\n                nex_mask = mask | (1<<i)\n                # case1: make sure that each node is only traversed once\n                # case2: only if we can get larger save length, we consider it.\n                if nex_mask != mask and d[mask][node] + G[node][i] >= d[nex_mask][i]:\n                    d[nex_mask][i] = d[mask][node] + G[node][i]\n                    Q.append((i, nex_mask, path+[i], d[nex_mask][i]))\n\n        return pathtoStr(A,G,P)\n```
[]