Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Repeated operations on the same interval form a path between rule strings. Operations on different intervals must be disjoint, so the full transformation can be split into nonoverlapping segments. This gives two levels: shortest paths price a segment, and dynamic programming chooses the segments.

Approach

Build a directed graph whose vertices are rule strings and whose weighted edges are conversions. Collect the distinct rule lengths. Cache shortest-path results for requested source/target substring pairs using the heap-based relaxation routine. Duplicate rules remain separate edges. JavaScript skips outdated heap entries; Python rescans them, without changing the resulting shortest distances.

Let dp(i) be the minimum cost to transform the suffix starting at i, with dp(n) = 0. If the current characters match, one option is to leave that character unchanged and use dp(i + 1). Also try each rule length that fits. Extract the two corresponding substrings; when the source substring is a key in the adjacency map, combine their conversion cost with dp(i + length). Take the minimum. Python's default dictionary can also acquire keys for reached vertices with no outgoing edges; considering those keys is harmless. Requested target substrings need not occur in any rule, and unreachable results are cached too.

Matching characters do not prevent trying a larger segment, which may be cheaper overall. Python memoizes this recurrence recursively; JavaScript evaluates it iteratively. Return -1 if the complete transformation remains unreachable.

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

        for s, e, w in zip(original, changed, cost):
            adj[s].append((w, e))
        
        @cache
        def dijkstra(s, t):
            d = defaultdict(lambda: inf)
            d[s] = 0
            h = [(0, s)] # (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[t]
        
        lengths = sorted(set(len(w) for w in original))

        @cache
        def dp(i):
            if i == len(source): return 0 # base case
            if source[i] == target[i]: best = dp(i + 1) # try next c and length
            else: best = inf # try lengths

            for length in lengths:
                if i + length > len(source): break
                s = source[i:i+length]
                t = target[i:i+length]
                if not s in adj: continue
                best = min(best, dijkstra(s, t) + dp(i + length))
            
            return best
        
        res = dp(0)
        return res if res != inf else -1

Complexity analysis

Let n be the string length, r the rule count including duplicates, U <= 2r the number of distinct rule strings, q the number of rule lengths, L the maximum rule length, and P <= nq the number of distinct substring pairs actually cached. P need not be bounded by U^2 because requested targets can be arbitrary substrings. With expected hash-table access and conservative O(L) string hashing/comparison/copying costs, let B = rL + qlog(q + 1) + nqL. JavaScript takes O(B + P((r + U)L + rlog(r + 1))) time. Python takes O(B + PL(U + r^2 + rlog(r + 1))) conservatively: it rescans stale entries, and heap ties can compare strings. A search enqueues O(r) entries. Auxiliary space is O(n + r + U + PL), including retained substring cache keys and one search's working state. Python additionally has O(n) recursive depth, which can exceed an unadjusted recursion limit; JavaScript's suffix DP is iterative.