Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A character conversion can pass through intermediate letters, so the cheapest direct rule is not necessarily the cheapest transformation. Treat letters as vertices and conversion rules as directed weighted edges. Then each position needs a shortest path from its source letter to its target letter.

Approach

Build an adjacency list containing all conversion rules, including repeated rules. Run the implementation's heap-based shortest-path search from each of the 26 letters, starting its own distance at zero and relaxing an edge whenever it improves the destination's recorded cost. Positive rule costs allow shortest-path reasoning. Store the resulting conversion costs. JavaScript skips outdated heap entries; Python scans their outgoing edges again. Such scans cannot improve any distance, since the smaller distance for that same vertex was already processed.

For each string position, look up the corresponding source-to-target distance. If it is unreachable, return -1; otherwise add it to the total. Positions can be changed independently, so summing their individual minimum costs gives the global minimum. An already matching character contributes zero without needing a conversion rule.

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        adj = defaultdict(list)
        for i in range(len(original)):
            adj[ord(original[i]) - ord('a')].append((cost[i], ord(changed[i]) - ord('a')))

        def dijkstra(i):
            d = [inf] * 26
            d[i] = 0
            h = [(0, i)] # w, node

            while h:
                w, node = heapq.heappop(h)
                for nw, nei in adj[node]:
                    if w + nw < d[nei]:
                        d[nei] = w + nw
                        heapq.heappush(h, (w + nw, nei))

            return d

        costs = [dijkstra(i) for i in range(26)]
        ans = 0

        for i in range(len(source)):
            s, t = ord(source[i]) - ord('a'), ord(target[i]) - ord('a')
            if costs[s][t] == inf:
                return -1
            ans += costs[s][t]

        return ans

Complexity analysis

Let n be the string length, r the number of rules including duplicates, and V = 26. JavaScript takes O(V * (V + r log(r + 1)) + n) time. Python does not skip stale heap entries, so a conservative time bound is O(V * (V + r^2 + r log(r + 1)) + n). Each search enqueues at most r + 1 entries, but Python may rescan up to r outgoing edges for each one; duplicate rules also prevent bounding heap size by V. Auxiliary space is O(V^2 + r) in both versions, including the adjacency lists, heap and stored distance tables.