{"id":10100,"date":"2024-01-08T06:01:15","date_gmt":"2024-01-08T14:01:15","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10100"},"modified":"2024-01-08T06:01:52","modified_gmt":"2024-01-08T14:01:52","slug":"leetcode-2976-minimum-cost-to-convert-string-i","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-2976-minimum-cost-to-convert-string-i\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2976. Minimum Cost to Convert String I"},"content":{"rendered":"\n

You are given two 0-indexed<\/strong> strings source<\/code> and target<\/code>, both of length n<\/code> and consisting of lowercase<\/strong> English letters. You are also given two 0-indexed<\/strong> character arrays original<\/code> and changed<\/code>, and an integer array cost<\/code>, where cost[i]<\/code> represents the cost of changing the character original[i]<\/code> to the character changed[i]<\/code>.<\/p>\n\n\n\n

You start with the string source<\/code>. In one operation, you can pick a character x<\/code> from the string and change it to the character y<\/code> at a cost of z<\/code> if<\/strong> there exists any<\/strong> index j<\/code> such that cost[j] == z<\/code>, original[j] == x<\/code>, and changed[j] == y<\/code>.<\/p>\n\n\n\n

Return the minimum<\/strong> cost to convert the string <\/em>source<\/code> to the string <\/em>target<\/code> using any<\/strong> number of operations. If it is impossible to convert<\/em> source<\/code> to<\/em> target<\/code>, return<\/em> -1<\/code>.<\/p>\n\n\n\n

Note<\/strong> that there may exist indices i<\/code>, j<\/code> such that original[j] == original[i]<\/code> and changed[j] == changed[i]<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> 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]\nOutput:<\/strong> 28\nExplanation:<\/strong> To convert the string \"abcd\" to string \"acbe\":\n- Change value at index 1 from 'b' to 'c' at a cost of 5.\n- Change value at index 2 from 'c' to 'e' at a cost of 1.\n- Change value at index 2 from 'e' to 'b' at a cost of 2.\n- Change value at index 3 from 'd' to 'e' at a cost of 20.\nThe total cost incurred is 5 + 1 + 2 + 20 = 28.\nIt can be shown that this is the minimum possible cost.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> source = \"aaaa\", target = \"bbbb\", original = [\"a\",\"c\"], changed = [\"c\",\"b\"], cost = [1,2]\nOutput:<\/strong> 12\nExplanation:<\/strong> To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> source = \"abcd\", target = \"abce\", original = [\"a\"], changed = [\"e\"], cost = [10000]\nOutput:<\/strong> -1\nExplanation:<\/strong> It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= source.length == target.length <= 105<\/sup><\/code><\/li>
  • source<\/code>, target<\/code> consist of lowercase English letters.<\/li>
  • 1 <= cost.length == original.length == changed.length <= 2000<\/code><\/li>
  • original[i]<\/code>, changed[i]<\/code> are lowercase English letters.<\/li>
  • 1 <= cost[i] <= 106<\/sup><\/code><\/li>
  • original[i] != changed[i]<\/code><\/li><\/ul>\n\n\n\n
    Solution: All pairs shortest path<\/strong><\/h2>\n\n\n\n
    Compute the shortest path (min cost) for any given letter pairs.<\/p>\n\n\n\n
    Time complexity: O(26^3 + m + n)
    Space complexity: O(26^2)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n    long long minimumCost(string s, string t, vector& o, vector& c, vector& cost) {\n    const int n = c.size();\n    vector> d(26, vector(26, 1e9));\n    for (int i = 0; i < 26; ++i)\n      d[i][i] = 0;\n    for (int i = 0; i < n; ++i)\n      d[o[i] - 'a'][c[i] - 'a'] = min(d[o[i] - 'a'][c[i] - 'a'], cost[i]);\n    for (int k = 0; k < 26; ++k)\n      for (int i = 0; i < 26;++i)\n        for (int j = 0; j < 26; ++j)\n          if (d[i][k] + d[k][j] < d[i][j])\n            d[i][j] = d[i][k] + d[k][j];\n    long ans = 0;\n    for (int i = 0; i < s.size(); ++i) {\n      if (d[s[i] - 'a'][t[i] - 'a'] >= 1e9) return -1; \n      ans += d[s[i] - 'a'][t[i] - 'a'];\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,177,87],"class_list":["post-10100","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-medium","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10100","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=10100"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10100\/revisions"}],"predecessor-version":[{"id":10102,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10100\/revisions\/10102"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10100"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10100"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10100"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}