Question

Code

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        

        adj = defaultdict(list)

        for o, c, co in zip(original, changed, cost):
            adj[o].append((co, c))

        memo = {}

        def min_cost(src):

            queue = [(0, src)]
            visited = set()


            while queue:
                cur_cost, cur_node = heapq.heappop(queue)
                
                if cur_node in visited:
                    continue
                
                visited.add(cur_node)

                memo[(src, cur_node)] = cur_cost

                for nei_cost, nei_node in adj[cur_node]:
                    if nei_node in visited:
                        continue
                    heapq.heappush(queue, (nei_cost + cur_cost, nei_node))

            return

        for i in range(26):
            min_cost(chr(ord('a') + i))

        
        res = 0
        for i in range(len(source)):
            if (source[i], target[i]) not in memo:
                return -1
            else:
                res += memo[(source[i], target[i])]

        return res