aboutsummaryrefslogtreecommitdiff
path: root/min_cost_convert_string1.py
diff options
context:
space:
mode:
Diffstat (limited to 'min_cost_convert_string1.py')
-rw-r--r--min_cost_convert_string1.py102
1 files changed, 102 insertions, 0 deletions
diff --git a/min_cost_convert_string1.py b/min_cost_convert_string1.py
new file mode 100644
index 0000000..cb9c4fc
--- /dev/null
+++ b/min_cost_convert_string1.py
@@ -0,0 +1,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]
+ )
+ )