Python Recursion with Memory
Many thanks to @ygt2016. The original code is here. I converted the code to recursion, which might be a little easier to understand. Hope this is helpful. \nThe
Many thanks to @ygt2016. The original code is [here](https://leetcode.com/problems/find-the-shortest-superstring/discuss/195077/Clean-python-DP-with-explanations). I converted the code to recursion, which might be a little easier to understand. Hope this is helpful. \nThe general idea is:\n1. Build a (dense) graph whose node `i` is the `i`th word in `A`. The weight on the arc `i-->j` is `graph[i][j]`, representing the length of the overlapping part between `A[i]` and `A[j]`.\n2. Then, our goal is to find an ordering of the words (nodes) `0,1,2,...,n-1` such that when the words are concatenated in this order, the total length is the smallest. Define the state as `(i,k)`, where `i` is a number whose binary form indicates which nodes are included in the ordering; `k` denotes the last node in the ordering. Let `memo[i,k]` be the shortest superstring when concatenating the words represented by the bits in `i` and with `k` as the last word. (You may call `memo` as `dp`, if you want.)\n3. The recursion part is `memo[i,k]=min(i ^ (1 << k), j)`, for all the bits `j` in the ordering `i` excluding `k` itself.\n4. Finally, what we are looking for is just the best result within `memo[(i << n) - 1, k]`, for all the `k` in `{0,1,2,...,n-1}`.\n```\nclass Solution:\n    def shortestSuperstring(self, A: List[str]) -> str:\n        n = len(A)\n        # Building the graph\n        graph = [[0] * n for _ in range(n)]\n        for i, word1 in enumerate(A):\n            for j, word2 in enumerate(A):\n                if i == j: continue\n                for k in range(min(len(word1), len(word2)))[::-1]:\n                    if word1[-k:] == word2[:k]:\n                        graph[i][j] = k\n                        break\n        \n        # Recursion. i is a mask to represent the ordering. k is the last node in the ordering.\n        memo = {}\n        def search(i, k):\n            if (i, k) in memo: return memo[i, k]\n            if not (i & (1 << k)): return \'\'\n            if i == (1 << k): return A[k]\n            memo[i, k] = \'\'\n            for j in range(n):\n                if j != k and i & (1 << j):\n                    candidate = search(i ^ (1 << k), j) + A[k][graph[j][k]:]\n                    if memo[i, k] == \'\' or len(candidate) < len(memo[i, k]):\n                        memo[i, k] = candidate\n            return memo[i, k]\n        \n        # Finding the best\n        res = \'\'\n        for k in range(n):\n            candidate = search((1 << n) - 1, k)\n            if res == \'\' or len(candidate) < len(res):\n                res = candidate\n        return res        \n```
[]