Clean python DP with explanations
python\nclass Solution:\n    def shortestSuperstring(self, A):\n        """\n        :type A: List[str]\n        :rtype: str\n        """\n        # construct a
```python\nclass Solution:\n    def shortestSuperstring(self, A):\n        """\n        :type A: List[str]\n        :rtype: str\n        """\n        # construct a directed graph\n        #   node i => A[i]\n        #   weights are represented as an adjacency matrix:\n        #   shared[i][j] => length saved by concatenating A[i] and A[j]\n        n = len(A)\n        shared = [[0] * n for _ in range(n)]\n        for i in range(n):\n            for j in range(n):\n                for k in range(min(len(A[i]), len(A[j])), -1, -1):\n                    if A[i][-k:] == A[j][:k]:\n                        shared[i][j] = k\n                        break\n\n        # The problem becomes finding the shortest path that visits all nodes exactly once.\n        # Brute force DFS would take O(n!) time.\n        # A DP solution costs O(n^2 2^n) time.\n        # \n        # Let\'s consider integer from 0 to 2^n - 1. \n        # Each i contains 0-n 1 bits. Hence each i selects a unique set of strings in A.\n        # Let\'s denote set(i) => {A[j] | j-th bit of i is 1}\n        # dp[i][k] => shortest superstring of set(i) ending with A[k]\n        #\n        # e.g. \n        #   if i = 6 i.e. 110 in binary. dp[6][k] considers superstring of A[2] and A[1].\n        #   dp[6][1] => the shortest superstring of {A[2], A[1]} ending with A[1].\n        #   For this simple case dp[6][1] = concatenate(A[2], A[1])\n        dp = [[\'\'] * 12 for _ in range(1 << 12)]\n        for i in range(1 << n):\n            for k in range(n):\n                # skip if A[k] is not in set(i) \n                if not (i & (1 << k)):\n                    continue\n                # if set(i) == {A[k]}\n                if i == 1 << k:\n                    dp[i][k] = A[k]\n                    continue\n                for j in range(n):\n                    if j == k:\n                        continue\n                    if i & (1 << j):\n                        # the shortest superstring if we remove A[k] from the set(i)\n                        s = dp[i ^ (1 << k)][j]\n                        s += A[k][shared[j][k]:]\n                        if dp[i][k] == \'\' or len(s) < len(dp[i][k]):\n                            dp[i][k] = s\n\n        min_len = float(\'inf\')\n        result = \'\'\n\n        # find the shortest superstring of all candidates ending with different string\n        for i in range(n):\n            s = dp[(1 << n) - 1][i]\n            if len(s) < min_len:\n                min_len, result = len(s), s\n        return result\n```\t\n\t\t
[]