Python3 - memoization with bitmask, clean solution
The idea is simple: first, let\'s store the overlapping for each pair of words. Second, for DP, during each iteration, we look at words[i]; we need to find a un
The idea is simple: first, let\'s store the overlapping for each pair of words. Second, for DP, during each iteration, we look at words[i]; we need to find a unused words[j] and consider to merge the two words together. \n\nFor example, words[i] is \'abcde\' and words[j] is \'cdef\', the merging of the two words will be \'abcdef\'. Out of all the possible outcomes, we take the one with minimum length during each iteration.\n\nHow do we find an unused word? We use bitmask to keep track of used/unused word. A bit \'1\' at position i means the words[i] has already been taken.\n\n```python\nclass Solution:\n    def shortestSuperstring(self, words: List[str]) -> str:\n        n = len(words)\n        overlaps = [[0 for _ in range(n)] for _ in range(n)]\n        for i in range(n):\n            for j in range(n):\n                if i == j:\n                    continue\n                x, y = words[i], words[j]\n                size = len(x)\n                for k in range(1, size):\n                    if y.startswith(x[k:]):\n                        overlaps[i][j] = size - k\n                        break\n\n        @lru_cache(None)\n        def helper(i, mask):\n            if mask == (1<<n) - 1:\n                return words[i]\n            ans = \'#\' * 320\n            for j in range(n):\n                if mask & (1<<j) == 0:\n                    k = overlaps[i][j]\n                    string = helper(j, mask | (1<<j))\n                    if len(words[i] + string[k:]) < len(ans):\n                        ans = words[i] + string[k:]\n            return ans\n\n        return min([helper(i, 1<<i) for i in range(n)], key=len)\n```
[]