{"id":9636,"date":"2022-04-09T23:20:27","date_gmt":"2022-04-10T06:20:27","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9636"},"modified":"2022-04-09T23:22:26","modified_gmt":"2022-04-10T06:22:26","slug":"leetcode-2232-minimize-result-by-adding-parentheses-to-expression","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-2232-minimize-result-by-adding-parentheses-to-expression\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2232. Minimize Result by Adding Parentheses to Expression"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> string expression<\/code> of the form \"<num1>+<num2>\"<\/code> where <num1><\/code> and <num2><\/code> represent positive integers.<\/p>\n\n\n\n

Add a pair of parentheses to expression<\/code> such that after the addition of parentheses, expression<\/code> is a valid<\/strong> mathematical expression and evaluates to the smallest<\/strong> possible value. The left parenthesis must<\/strong> be added to the left of '+'<\/code> and the right parenthesis must<\/strong> be added to the right of '+'<\/code>.<\/p>\n\n\n\n

Return expression<\/code> after adding a pair of parentheses such that <\/em>expression<\/code> evaluates to the smallest<\/strong> possible value.<\/em> If there are multiple answers that yield the same result, return any of them.<\/p>\n\n\n\n

The input has been generated such that the original value of expression<\/code>, and the value of expression<\/code> after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.<\/p>\n\n\n\n

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

Input:<\/strong> expression = \"247+38\"\nOutput:<\/strong> \"2(47+38)\"\nExplanation:<\/strong> The expression<\/code> evaluates to 2 * (47 + 38) = 2 * 85 = 170.\nNote that \"2(4)7+38\" is invalid because the right parenthesis must be to the right of the '+'<\/code>.\nIt can be shown that 170 is the smallest possible value.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> expression = \"12+34\"\nOutput:<\/strong> \"1(2+3)4\"\nExplanation:<\/strong> The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> expression = \"999+999\"\nOutput:<\/strong> \"(999+999)\"\nExplanation:<\/strong> The expression<\/code> evaluates to 999 + 999 = 1998.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 3 <= expression.length <= 10<\/code><\/li>
  • expression<\/code> consists of digits from '1'<\/code> to '9'<\/code> and '+'<\/code>.<\/li>
  • expression<\/code> starts and ends with digits.<\/li>
  • expression<\/code> contains exactly one '+'<\/code>.<\/li>
  • The original value of expression<\/code>, and the value of expression<\/code> after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.<\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Try all possible positions to add parentheses and evaluate the new expression.<\/p>\n\n\n\n
    Time complexity: O(n2<\/sup>)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string minimizeResult(string expression) {\n    const int n = expression.size();\n    auto p = expression.find('+');\n    int best = INT_MAX;\n    string ans;\n    for (int l = 0; l < p; ++l)\n      for (int r = p + 2; r < n + 1; ++r) {\n        const int m1 = l ? stoi(expression.substr(0, l)) : 1;\n        const int m2 = (r < n) ? stoi(expression.substr(r)) : 1;\n        const int n1 = stoi(expression.substr(l, p));\n        const int n2 = stoi(expression.substr(p + 1, r - p - 1));\n        const int cur = m1 * (n1 + n2) * m2;\n        if (cur < best) {\n          best = cur;\n          ans = expression;\n          ans.insert(l, \"(\");\n          ans.insert(r + 1, \")\");\n        }\n      }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a 0-indexed string expression of the form “<num1>+<num2>” where <num1> and <num2> represent positive integers. Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[173,177,421,4],"class_list":["post-9636","post","type-post","status-publish","format-standard","hentry","category-string","tag-expression","tag-medium","tag-parentheses","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9636","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=9636"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9636\/revisions"}],"predecessor-version":[{"id":9638,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9636\/revisions\/9638"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9636"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9636"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9636"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}