[Python3] travelling sales person (TSP)
\n\nclass Solution:\n    def shortestSuperstring(self, words: List[str]) -> str:\n        n = len(words)\n        graph = [[0]*n for _ in range(n)] # graph as a
\n```\nclass Solution:\n    def shortestSuperstring(self, words: List[str]) -> str:\n        n = len(words)\n        graph = [[0]*n for _ in range(n)] # graph as adjacency matrix \n        \n        for i in range(n):\n            for j in range(n): \n                if i != j: \n                    for k in range(len(words[j])): \n                        if words[i].endswith(words[j][:k]): \n                            graph[i][j] = len(words[j]) - k \n                            \n        @cache\n        def fn(prev, mask): \n            """Return length of shortest superstring & current choice of word."""\n            if mask == 0: return 0, None\n            vv, kk = inf, None\n            for k in range(n): \n                if mask & 1<<k: \n                    v, _ = fn(k, mask ^ 1<<k)\n                    offset = len(words[k]) if prev == -1 else graph[prev][k]\n                    if v + offset < vv: vv, kk = v + offset, k\n            return vv, kk\n        \n        ans = []\n        prev = -1 \n        mask = (1<<n) - 1\n        while mask: \n            _, k = fn(prev, mask)\n            if ans: ans.append(words[k][-graph[prev][k]:])\n            else: ans.append(words[k])\n            prev = k\n            mask ^= 1<<k \n        return "".join(ans)\n```
['Python3']