aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-07-26 19:10:45 -0600
committerJack Sangdahl <[email protected]>2024-07-26 19:10:45 -0600
commit9b1687331bb6385e4ae676b1be5482d3c2156fd4 (patch)
tree0b8b7fbeb2f4bce948b7576e0e3bf46e33431426
parent9cf0377981d56592712e0b7e48b58daa10c719fb (diff)
downloadleetcode-9b1687331bb6385e4ae676b1be5482d3c2156fd4.tar.gz
leetcode-9b1687331bb6385e4ae676b1be5482d3c2156fd4.zip
2976. minimum cost to convert string 1
-rw-r--r--min_cost_convert_string1.cpp51
-rw-r--r--min_cost_convert_string1.py102
2 files changed, 153 insertions, 0 deletions
diff --git a/min_cost_convert_string1.cpp b/min_cost_convert_string1.cpp
new file mode 100644
index 0000000..914eff9
--- /dev/null
+++ b/min_cost_convert_string1.cpp
@@ -0,0 +1,51 @@
+// 2976. Minimum Cost to Convert String I
+#include "leetcode.h"
+
+/*
+ * 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 {
+public:
+ long long minimumCost(string source, string target, vector<char> &original,
+ vector<char> &changed, vector<int> &cost) {
+ long long ans = 0;
+ vector<vector<long long>> n(26, vector<long long>(26, INT_MAX));
+ for (int i = 0; i < original.size(); ++i) {
+ int s = original[i] = 'a', t = changed[i] - 'a';
+ n[s][t] = min(n[s][t], (long long)cost[i]);
+ }
+ for (int k = 0; k < 26; ++k)
+ for (int i = 0; i < 26; i++)
+ for (int j = 0; j < 26; j++)
+ n[i][j] = min(n[i][j], n[i][k] + n[k][j]);
+ for (int i = 0; i < source.size(); ++i) {
+ if (source[i] == target[i])
+ continue;
+ int s = source[i] - 'a', t = target[i] - 'a';
+ if (n[s][t] >= INT_MAX)
+ return -1;
+ ans += n[s][t];
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<char> o1 = {'a', 'b', 'c', 'c', 'e', 'd'},
+ ch1 = {'b', 'c', 'b', 'e', 'b', 'e'}, o2 = {'a', 'b'},
+ ch2 = {'c', 'b'}, o3 = {'a'}, ch3 = {'e'};
+ vector<int> co1 = {2, 5, 5, 1, 2, 20}, co2 = {1, 2}, co3 = {10000};
+ printf("%lld\n", obj.minimumCost("abcd", "acbe", o1, ch1, co1)); // expect: 28
+ printf("%lld\n", obj.minimumCost("aaaa", "bbbb", o2, ch2, co2)); // expect: 12
+ printf("%lld\n", obj.minimumCost("abcd", "acbe", o3, ch3, co3)); // expect: -1
+}
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]
+ )
+ )