# Untitled

unknown
python
2 months ago
3.4 kB
5
Indexable
Never
```
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
# pruning
continue

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)