Easy to understand TSP implementation (Top-Down/Bottom-Up)[python]
Approach\n Describe your approach to solving the problem. \nConsider this problem as a graph problem where we need to visit every single node with the minimal o
# Approach\n<!-- Describe your approach to solving the problem. -->\nConsider this problem as a graph problem where we need to visit every single node with the minimal overall cost. The words will be our nodes and the nonOverlapping substring between two words will be our cost.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2 * 2^n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n * 2^n)$$\n\n# Code\n\n### Easy to understand - Top-Down DP\n```\nclass Solution:\n    def shortestSuperstring(self, words: List[str]) -> str:\n        n = len(words)\n        overlap = [[\'\'] * n for _ in range(n)]\n\n        def getOverlap(a, b):\n            l, i = 0, 1\n            while i <= min(len(a), len(b)):\n                if a[len(a)-i:] == b[:i]:\n                    l = i\n                i += 1\n            return b[l:]\n\n        for i in range(n):\n            for j in range(n):\n                if i != j: overlap[i][j] = getOverlap(words[i], words[j])\n\n        def TSP(prev, mask, dp):\n            if (prev, mask) in dp: return dp[(prev, mask)]\n            if mask == ((1 << n) - 1): return \'\'\n            ans = \'*\' * 1000000\n            for i in range(n):\n                if mask & (1 << i): continue\n                word = overlap[prev][i] if prev != -1 else words[i]\n                ans = min(ans, word + TSP(i, mask | (1 << i), dp), key=len)\n            dp[(prev, mask)] = ans\n            return ans\n\n        return TSP(-1, 0, {})\n```\n\n### Bottom-Up DP\nNotice here that we apply a push-dp instead of a pull-dp. That is because, there is no way for us to know in advance what the best string would be for a mask (7) or (111) where all the strings will be included where n = 3.\n\nTherefore we start with a base case where only one string will be included and we build our dp by pushing values forward in the mask.\n\nFinally, we get the minimum string with all words included (mask = ($$2^n - 1$$))\n```\nclass Solution:\n    def shortestSuperstring(self, words: List[str]) -> str:\n        n = len(words)\n        overlap = [[\'\'] * n for _ in range(n)]\n\n        def getOverlap(a, b):\n            l, i = 0, 1\n            while i <= min(len(a), len(b)):\n                if a[len(a)-i:] == b[:i]:\n                    l = i\n                i += 1\n            return b[l:]\n\n        for i in range(n):\n            for j in range(n):\n                if i != j: overlap[i][j] = getOverlap(words[i], words[j])\n        ans = \'*\' * (10**4)\n        dp = [[ans] * (1 << n) for _ in range(n)]\n        for i in range(n): dp[i][(1 << i)] = words[i]\n\n        for mask in range(1, 1 << n):\n            for i in range(n):\n                if mask & (1 << i):\n                    for j in range(n):\n                        if i != j and mask & (1 << j): continue\n                        dp[j][mask | (1 << j)] = min(dp[j][mask | (1 << j)], dp[i][mask] + overlap[i][j], key=len)\n\n        for i in range(n): ans = min(ans, dp[i][(1 << n) - 1], key=len)\n        return ans\n```
['Bit Manipulation', 'Graph', 'Bitmask', 'Python3']