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
Leave a Comment