diff options
author | Jack Sangdahl <[email protected]> | 2024-07-26 19:10:45 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-07-26 19:10:45 -0600 |
commit | 9b1687331bb6385e4ae676b1be5482d3c2156fd4 (patch) | |
tree | 0b8b7fbeb2f4bce948b7576e0e3bf46e33431426 | |
parent | 9cf0377981d56592712e0b7e48b58daa10c719fb (diff) | |
download | leetcode-9b1687331bb6385e4ae676b1be5482d3c2156fd4.tar.gz leetcode-9b1687331bb6385e4ae676b1be5482d3c2156fd4.zip |
2976. minimum cost to convert string 1
-rw-r--r-- | min_cost_convert_string1.cpp | 51 | ||||
-rw-r--r-- | min_cost_convert_string1.py | 102 |
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] + ) + ) |