[Python] 80ms A* algorithm
Using ordinary TSP DP solution will try out every possible permutation and this is very time-consuming.\nSo I decided to use A algorithm to achieve some pruning
Using ordinary TSP DP solution will try out every possible permutation and this is very time-consuming.\nSo I decided to use A* algorithm to achieve some pruning.\n\nModel the directed graph:\n1. node: a pair of state and last inserted string\'s index, as (state, last)\n2. edge: represent the number of characters need to be inserted from (state, last) to (state | new_last, new_last)\n3. goal: find the shortest path from (0, None) to (target, *)\n\nI use state compression to represent the usage of strings. For example, "0b\'1101" means I have used strings of index 0, 2 and 3.\n\nFor A* alogrithm, if the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal. https://en.wikipedia.org/wiki/A*_search_algorithm\nTherefore, if we can come up with an underestimate heuristic function, we can ensure A* algorithm will return the answer we want.\n\nWe first calcualte the discount matrix, M[i][j] means how many more chatacters we need to insert A[j] after A[i]. For example, S[i] = "abcd" and S[j] = "abcdef", we only need to insert 2 more chatacters and M[i][j] = 2.\n\nAfter the calculation, we know the lowest number of chatacters for insertion for each string, and we use them as our heuristic function. More specifically, given a state, if a string has not yet been inserted, we add the lowest number of characters to our guess.\nThis heuristic function is guaranteed to not overestimate.\n\nThe remaining part is just implementing.\n\n```\nclass Solution:\n    def calcuclate_discount_matrix(self, A):\n        Trie = lambda : collections.defaultdict(Trie)\n        M = []\n        for i in range(len(A)):\n            # construct suffix trie\n            row, root = [], Trie()\n            for j in range(len(A[i])):\n                functools.reduce(dict.__getitem__, A[i][j:], root)[\'#\'] = True\n            # calculate the discount\n            for j in range(len(A)):\n                if i == j:\n                    row.append(float(\'inf\'))\n                    continue\n                word, discount, cur = A[j], 0, root\n                for k in range(len(word)):\n                    if word[k] not in cur:\n                        break\n                    cur = cur[word[k]]\n                    if \'#\' in cur:\n                        discount = k + 1\n                row.append(len(word) - discount)\n            M.append(row)\n        M.append(list(map(len, A)))\n        return M\n    \n    def shortestSuperstring(self, A: List[str]) -> str:\n        count = len(A)\n        target = (1 << count) - 1\n        \n        M = self.calcuclate_discount_matrix(A)\n\n        # an underestimate heuristic function\n        # we estimate the cost from current state to the final target:\n        # why underestimate? we choose every string\'s shortest version for concatenation.\n        min_cost = [min(M[j][i] for j in range(count)) for i in range(count)]\n        def heuristic(state):\n            return sum(min_cost[i] for i in range(count) if state & (1 << i) == 0)\n\n        seen = [[float(\'inf\')] * (1 + count) for _ in range(target + 1)]\n        \n        mini, sequence = float(\'inf\'), []\n        prio = [(0, 0, 0, count, [])]\n        while prio and prio[0][0] < mini:\n            _, cost, state, last, seq = heapq.heappop(prio)\n            \n            if seen[state][last] <= cost:\n                continue\n            seen[state][last] = cost\n            \n            if state == target:\n                if mini > cost:\n                    mini, sequence = cost, seq\n                continue\n            \n            costs = M[last]\n            for i in range(count):\n                mask = 1 << i\n                if state & mask == 0:\n                    total = cost + costs[i] + heuristic(state | mask)\n                    if total < seen[state | mask][i]:\n                        heapq.heappush(prio, (total, cost + costs[i], state | mask, i, seq + [i]))\n        \n        # reconstruct the answer\n        answer, state, last = [], 0, count\n        for nex in sequence:\n            answer.append(A[nex][(len(A[nex]) - M[last][nex]):])\n            state, last = state | (1 << nex), nex\n        \n        return \'\'.join(answer)\n\n\t# this part is just the ordinary TSP DP solution, 1100ms\n    def shortestSuperstring_DP_TSP(self, A: List[str]) -> str:\n        count = len(A)\n        target = (1 << count) - 1\n        \n        M = []\n        for i in range(count):\n            a, row = A[i], []\n            for j in range(count):\n                if i == j:\n                    row.append(float(\'inf\'))\n                    continue\n                b = A[j]\n                for k in range(len(b), -1, -1):\n                    if a.endswith(b[:k]):\n                        row.append(len(b) - k)\n                        break\n            M.append(row)\n\n        M.append(list(map(len, A)))\n        path = [[float(\'inf\')] * (1 + count) for _ in range(target + 1)]\n        DP = [[float(\'inf\')] * (1 + count) for _ in range(target + 1)]\n        DP[-1] = [0] * count\n\n        for state in range(target - 1, -1, -1):\n            for last in range(count + 1):\n                nex, costs = -1, M[last]\n                for i in range(count):\n                    mask = 1 << i\n                    if state & mask == 0:\n                        t = costs[i] + DP[state | mask][i]\n                        if t < DP[state][last]:\n                            nex, DP[state][last] = i, t\n                path[state][last] = nex        \n        \n#         path = {}\n#         functools.lru_cache(None)\n#         def helper(state, last):\n#             if state == target:\n#                 return 0\n            \n#             nex, answer, costs = None, float(\'inf\'), M[last]\n#             for i in range(count):\n#                 mask = 1 << i\n#                 if state & mask == 0:\n#                     t = costs[i] + helper(state | mask, i)\n#                     if t < answer:\n#                         nex, answer = i, t\n#             path[(state, last)] = nex\n#             return answer\n#         helper(0, count)\n        \n        answer, state, last = [], 0, count\n        for _ in range(count):\n            nex = path[state][last]\n            answer.append(A[nex][(len(A[nex]) - M[last][nex]):])\n            state, last = state | (1 << nex), nex\n        \n        return \'\'.join(answer)\n```
[]