1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
# 2976. Minimum Cost to Convert String I
from collections import defaultdict
import heapq
"""
you are given two 0 indexed strings 'source' and 'target', both of length 'n'
and consisting of lowercase english letters. you are also given two 0 indexed
character arrays 'original' and 'changed', and an integer array 'cost' where
'cost[i]' represents the cost of changing the character 'original[i]' to the
character 'changed[i]' you start with the string 'source'. in one operation,
you can pick a character 'x' from te string and change it to the character
'y' at a cost of 'z' if there exists any index 'j' such that 'cost[j] == z,
original[j] == x, changed[j] == y'. return the minimum cost to conver the
string 'source' to the string 'target'.
"""
class Solution(object):
def minimumCost(self, source, target, original, changed, cost):
"""
:type source: str
:type target: str
:type original: List[str]
:type changed: List[str]
:type cost: List[int]
:rtype: int
"""
def build(original, changed, costs):
graph = defaultdict(lambda: defaultdict(lambda: float("inf")))
for ori, ch, cost in zip(original, changed, costs):
graph[ori][ch] = min(graph[ori][ch], cost)
return graph
def dijkstra(graph, start_node, target_node):
if start_node not in graph:
return float("inf")
visited_nodes = set()
min_heap = [(0, start_node)]
while min_heap:
cost_to_current, current_node = heapq.heappop(min_heap)
if current_node == target_node:
return cost_to_current
if current_node in visited_nodes:
continue
visited_nodes.add(current_node)
for neighbor_node in graph[current_node]:
if neighbor_node not in visited_nodes:
heapq.heappush(
min_heap,
(
cost_to_current + graph[current_node][neighbor_node],
neighbor_node,
),
)
return float("inf")
graph = build(original, changed, cost)
total_cost = 0
memo = {}
for s, t in zip(source, target):
if s != t:
if (s, t) in memo:
cost = memo[(s, t)]
else:
cost = dijkstra(graph, s, t)
memo[(s, t)] = cost
if cost == float("inf"):
return -1
total_cost += cost
return total_cost
if __name__ == "__main__":
obj = Solution()
print(
obj.minimumCost(
source="abcd",
target="acbe",
original=["a", "b", "c", "c", "e", "d"],
changed=["b", "c", "b", "e", "b", "e"],
cost=[2, 5, 5, 1, 2, 20],
)
)
print(
obj.minimumCost(
source="aaaa",
target="bbbb",
original=["a", "c"],
changed=["c", "b"],
cost=[1, 2],
)
)
print(
obj.minimumCost(
source="abcd", target="abce", original=["a"], changed=["e"], cost=[10000]
)
)
|