{"id":9314,"date":"2021-12-31T12:32:39","date_gmt":"2021-12-31T20:32:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9314"},"modified":"2021-12-31T12:33:45","modified_gmt":"2021-12-31T20:33:45","slug":"leetcode-1946-largest-number-after-mutating-substring","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1946-largest-number-after-mutating-substring\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1946. Largest Number After Mutating Substring"},"content":{"rendered":"\n

You are given a string num<\/code>, which represents a large integer. You are also given a 0-indexed<\/strong> integer array change<\/code> of length 10<\/code> that maps each digit 0-9<\/code> to another digit. More formally, digit d<\/code> maps to digit change[d]<\/code>.<\/p>\n\n\n\n

You may choose<\/strong> to mutate a single substring<\/strong> of num<\/code>. To mutate a substring, replace each digit num[i]<\/code> with the digit it maps to in change<\/code> (i.e. replace num[i]<\/code> with change[num[i]]<\/code>).<\/p>\n\n\n\n

Return a string representing the largest<\/strong> possible integer after mutating<\/strong> (or choosing not to) a single substring<\/strong> of <\/em>num<\/code>.<\/p>\n\n\n\n

A substring<\/strong> is a contiguous sequence of characters within the string.<\/p>\n\n\n\n

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

Input:<\/strong> num = \"132\", change = [9,8,5,0,3,6,4,2,6,8]\nOutput:<\/strong> \"832\"\nExplanation:<\/strong> Replace the substring \"1\":\n- 1 maps to change[1] = 8.\nThus, \"132\" becomes \"832\".\n\"832\" is the largest number that can be created, so return it.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> num = \"021\", change = [9,4,3,5,7,2,1,9,0,6]\nOutput:<\/strong> \"934\"\nExplanation:<\/strong> Replace the substring \"021\":\n- 0 maps to change[0] = 9.\n- 2 maps to change[2] = 3.\n- 1 maps to change[1] = 4.\nThus, \"021\" becomes \"934\".\n\"934\" is the largest number that can be created, so return it.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> num = \"5\", change = [1,4,7,5,3,2,5,6,9,4]\nOutput:<\/strong> \"5\"\nExplanation:<\/strong> \"5\" is already the largest number that can be created, so return it.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= num.length <= 105<\/sup><\/code><\/li>
  • num<\/code> consists of only digits 0-9<\/code>.<\/li>
  • change.length == 10<\/code><\/li>
  • 0 <= change[d] <= 9<\/code><\/li><\/ul>\n\n\n\n
    Solution: Greedy<\/strong><\/h2>\n\n\n\n
    Find the first digit that is less equal to the mutated one as the start of the substring, keep replacing as long as mutated >= current.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string maximumNumber(string num, vector& change) {\n    const int n = num.size();\n    for (int i = 0; i < n; ++i)\n      if (num[i] - '0' < change[num[i] - '0']) {\n        for (int j = i; j < n && num[j] - '0' <= change[num[j] - '0']; ++j)\n          num[j] = change[num[j] - '0'] + '0';\n        break;\n      }\n    return num;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    You are given a string num, which represents a large integer. You are also given a 0-indexed integer array change of length 10 that maps each digit 0-9 to another digit. More formally, digit d maps…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177,753,314],"class_list":["post-9314","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-replacing","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9314","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=9314"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9314\/revisions"}],"predecessor-version":[{"id":9316,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9314\/revisions\/9316"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9314"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9314"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9314"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}