aboutsummaryrefslogtreecommitdiff
path: root/min_cost_convert_string1.py
blob: cb9c4fcb91bf0750d714610593d8c0d0e9916ee9 (plain)
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]
        )
    )