Untitled

from collections import defaultdict, Counter

MOD = 10**9 + 7

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

        def charCode(char):
            return ord(char) - ord('a') + 1

        # precomputing all hashes so we can easily look them up as needed
        def getAllSubstringHashes(string):
            hashes = {}
            for i in range(len(string)):
                hash = 0
                for j in range(i, len(string)):
                    hash *= 26
                    hash += charCode(string[j])
                    hash %= MOD
                    hashes[(i, j)] = hash
            return hashes
        
        sourceHashes = getAllSubstringHashes(source)
        targetHashes = getAllSubstringHashes(target)

        def getWordHash(word):
            hash = 0
            for char in word:
                hash *= 26
                hash += charCode(char)
                hash %= MOD
            return hash
        
        originalHashes = [getWordHash(word) for word in original]
        changedHashes = [getWordHash(word) for word in changed]


        # djikstra's from a hash to a hash, cached so we only compute each case once
        edgeMap = collections.defaultdict(lambda: defaultdict(lambda: float('inf')))
        for i in range(len(original)):
            edgeMap[originalHashes[i]][changedHashes[i]] = min(edgeMap[originalHashes[i]][changedHashes[i]], cost[i])
        cache = {}
        def djikstra(start, end):
            if (start, end) in cache:
                return cache[(start, end)]
            # print(f'djikstra called on start hash: {start} end hash: {end}')
            shortest = defaultdict(lambda: float('inf'))
            heap = [(0, start)] # distance, node letter

            while heap:
                cost, char = heapq.heappop(heap)
                if cost >= shortest[char]:
                    continue
                shortest[char] = cost
                for adj in edgeMap[char]:
                    newCost = cost + edgeMap[char][adj]
                    # pruning
                    if shortest[adj] <= newCost:
                        continue

                    heapq.heappush(heap, [newCost, adj])
            res = shortest[end]
            cache[(start, end)] = res
            return res

        # DP function, for each index, we consider changing all possible [i:r], use djikstra's to get the minimum cost, and rolling hash to lookup the hashcodes
        memo = [-1] * len(source)
        def dp(i):
            # base case
            if i == len(source):
                return 0

            if memo[i] != -1:
                return memo[i]

            resThis = float('inf')
            # we can skip this letter
            if source[i] == target[i]:
                resThis = dp(i + 1)

            # the region we change is i:r
            for r in range(i, len(source)):
                currHash = sourceHashes[(i, r)]
                desiredHash = targetHashes[(i, r)]
                djikstraCost = djikstra(currHash, desiredHash)
                resAdj = djikstraCost + dp(r + 1)
                resThis = min(resThis, resAdj)
            memo[i] = resThis
            return resThis

        res = dp(0)
        if res == float('inf'):
            return -1
        return res