Python3 - Top Down BitMask DP
As the question mentions that no string in A will be substring of another string in A. I can conclude that we can find our answer by one of the permutations of 
As the question mentions that no string in A will be substring of another string in A. I can conclude that we can find our answer by one of the permutations of combining different strings in A. If you combine two strings in A - like a + b, you can count the largest suffix of a which is also prefix of b. So I have a helper function which gives me this number.\nThen a + b become a + b[commonPart:].\nFirst TLE solution that I tried was generating all permutations of A and finding the minimum length. This was N! (12!) which can\'t pass. \nBut we can use the fact that most of the parts of the permutations are repetitive and we can somehow convert them to DP. Then I tried DP with bitmasking where state is -\n(i, bitmask) which means minimum length string that ends with A[i] and contains all elements in the bitmask.\n```\nclass Solution:\n    def shortestSuperstring(self, A: List[str]) -> str:\n        def commonSuffix(a, b):\n            for i in range(len(a)):\n                if a[i:] == b[:len(a)-i]:\n                    return len(a) - i\n            return 0\n        N = len(A)\n        from functools import lru_cache\n        @lru_cache(None)\n        def minString(last_index, bitmask):\n            if bitmask == (1<<N)-1:\n                return ""\n            current = "Z"*250\n            for i in range(N):\n                if not ((1<<i) & bitmask):\n                    current = min(\n                        current,\n                        A[i][commonSuffix(A[last_index], A[i]):] + minString(i, bitmask | (1<<i)),\n                        key=len\n                    )\n            return current\n        ans = "Z"*250\n        for i in range(N):\n            ans = min(ans, A[i] + minString(i, 1<<i), key=len)\n        return ans\n```
[]