[Python] dp on subsets solution  - 3 solutions + oneliner, explained
This is actually Travelling salesman problem (TSP) problem: if we look at our strings as nodes, then we can evaluate distance between one string and another, fo
This is actually Travelling salesman problem (TSP) problem: if we look at our strings as nodes, then we can evaluate distance between one string and another, for example for `abcde` and `cdefghij` distance is 5, because we need to use 5 more symbols `fghij` to continue first string to get the second. Note, that this is not symmetric, so our graph is oriented. \n\nThen our problem is equivalent to Traveling Salesman Problem (TSP): we need to find path with smallest weight, visiting all nodes. Here we have `2^n * n` possible states, where state consists of two elements:\n1. `mask`: binary mask with length n with already visited nodes.\n2. `last`: last visited node.\n3. In each `dp[mask][last]` we will keep length of built string + built string itself.\n\n#### Complexity \nThere will be `O(n)` possible transitions for each state: for example to the state `(10011101, 7)` we will have possible steps from `(00011101, 0), (00011101, 2), (00011101, 3), (00011101, 4)`. Finally, time complexity is `O(2^n*n^2*M)`, where `M` is the length of answer and space complexity is `O(2^n*n*M)` as well.\n\n```python\nclass Solution:\n    def shortestSuperstring(self, A):\n        @lru_cache(None)\n        def connect(w1, w2):\n            return [w2[i:] for i in range(len(w1) + 1) if w1[-i:] == w2[:i] or not i][-1]\n            \n        N = len(A) \n        dp = [[(float("inf"), "")] * N for _ in range(1<<N)]\n        for i in range(N): dp[1<<i][i] = (len(A[i]), A[i])\n            \n        for mask in range(1<<N):\n            n_z_bits = [j for j in range(N) if mask & 1<<j]\n            \n            for j, k in permutations(n_z_bits, 2):\n                cand = dp[mask ^ 1<<j][k][1] + connect(A[k], A[j])\n                dp[mask][j] = min(dp[mask][j], (len(cand), cand))\n\n        return min(dp[-1])[1]\n```\n\n#### Solution 2\nIdea is exactly the same as in previous solutoin, but here we can use functionaliry of `lru_cache`.\n\n#### Complexity\nis the same as Solution 1.\n\n#### Code\n```python\nclass Solution:\n    def shortestSuperstring(self, A):\n        @lru_cache(None)\n        def suff(w1, w2):\n            return [w2[i:] for i in range(len(w1) + 1) if w1[-i:] == w2[:i] or not i][-1]\n        \n        @lru_cache(None)\n        def dp(mask, l):\n            if mask + 1 == 1<<N: return ""\n            return min([suff(A[l], A[i]) + dp(mask | 1<<i, i) for i in range(N) if not mask & 1<<i], key = len)\n        \n        N = len(A)\n        return min([A[i] + dp(1<<i, i) for i in range(N)], key=len)\n```\n\nOr you can write it very long, but oneliner\n```python\nreturn (lambda f, c: min([A[i] + f(1<<i, i, c) for i in range(len(A))], key=len))((f := lambda m, l, c: c.get((m, l)) or c.setdefault((m,l), "" if m + 1 == 1<<len(A) else min([next(A[i][j:] for j in range(len(A[i]), -1, -1) if A[l].endswith(A[i][:j])) + f(m | 1<<i, i, c) for i in range(len(A)) if not m & 1<<i], key = len))), {})\n\n```\n\n#### Solution 3\n\nHere is improvement, which potentially will work faster for big strings: instead of keeping built string for every state, we keep only its length and connection to previous node. \n\n#### Complexity \nHere time and space complexity is `O(2^n*n^2)`, without constant `M`. However in practice it works just a bit faster, because of testcases.\n\n```python\nclass Solution:\n    def shortestSuperstring(self, A):\n        @lru_cache(None)\n        def connect(w1, w2):\n            return [(w2[i:], len(w2) - i) for i in range(len(w1) + 1) if w1[-i:] == w2[:i] or not i][-1]\n        \n        N = len(A)\n        dp = [[(float("inf"), -1)] * N for _ in range(1<<N)]\n        for i in range(N): dp[1<<i][i] = (len(A[i]), -1)\n            \n        for mask in range(1<<N):\n            n_z_bits = [j for j in range(N) if mask & 1<<j]\n            for j, k in permutations(n_z_bits, 2):\n                dp[mask][j] = min(dp[mask][j], (dp[mask ^ 1<<j][k][0] + connect(A[k], A[j])[1], k))\n                \n        mask = (1<<N) - 1\n        prev = min(dp[mask])\n        last = dp[mask].index(prev)\n        prev = prev[1]\n        ans = ""\n        \n        while prev != -1:\n            ans = connect(A[prev], A[last])[0] + ans\n            mask -= (1<<last)\n            prev, last = dp[mask][prev][1], prev\n            \n        return A[last] + ans\n```\n\n#### Remark \nLet me know if you know how to write the solution 3 in shorter way, I think code is too long.\nAlso see my collections of similar problems: https://leetcode.com/discuss/general-discussion/1125779/dynamic-programming-on-subsets-with-examples-explained\n\nAlso something wrong with test cases, if you just `return A`, it will be accepted! @leetcode, please fix this.\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**\n\n
['Dynamic Programming', 'Bitmask']