Skip to content

2232. Minimize Result by Adding Parentheses to Expression 👎

  • Time: $O((\log n)^4)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  string minimizeResult(string expression) {
    const int plusIndex = expression.find('+');
    const string left = expression.substr(0, plusIndex);
    const string right = expression.substr(plusIndex + 1);
    string ans;
    int mn = INT_MAX;

    // the expression -> a * (b + c) * d
    for (int i = 0; i < left.length(); ++i)
      for (int j = 0; j < right.length(); ++j) {
        const int a = i == 0 ? 1 : stoi(left.substr(0, i));
        const int b = stoi(left.substr(i));
        const int c = stoi(right.substr(0, j + 1));
        const int d = j == right.length() - 1 ? 1 : stoi(right.substr(j + 1));
        const int val = a * (b + c) * d;
        if (val < mn) {
          mn = val;
          ans = (i == 0 ? "" : to_string(a)) + '(' + to_string(b) + '+' +
                to_string(c) + ')' +
                (j == right.length() - 1 ? "" : to_string(d));
        }
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public String minimizeResult(String expression) {
    final int plusIndex = expression.indexOf('+');
    final String left = expression.substring(0, plusIndex);
    final String right = expression.substring(plusIndex + 1);
    String ans = "";
    int mn = Integer.MAX_VALUE;

    // the expression -> a * (b + c) * d
    for (int i = 0; i < left.length(); ++i)
      for (int j = 0; j < right.length(); ++j) {
        final int a = i == 0 ? 1 : Integer.parseInt(left.substring(0, i));
        final int b = Integer.parseInt(left.substring(i));
        final int c = Integer.parseInt(right.substring(0, j + 1));
        final int d = j == right.length() - 1 ? 1 : Integer.parseInt(right.substring(j + 1));
        final int val = a * (b + c) * d;
        if (val < mn) {
          mn = val;
          ans = (i == 0 ? "" : String.valueOf(a)) + '(' + String.valueOf(b) + '+' +
                String.valueOf(c) + ')' + (j == right.length() - 1 ? "" : String.valueOf(d));
        }
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def minimizeResult(self, expression: str) -> str:
    plusIndex = expression.index('+')
    left = expression[:plusIndex]
    right = expression[plusIndex + 1:]
    ans = ''
    mn = math.inf

    # the expression -> a * (b + c) * d
    for i in range(len(left)):
      for j in range(len(right)):
        a = 1 if i == 0 else int(left[:i])
        b = int(left[i:])
        c = int(right[0:j + 1])
        d = 1 if j == len(right) - 1 else int(right[j + 1:])
        val = a * (b + c) * d
        if val < mn:
          mn = val
          ans = (('' if i == 0 else str(a)) +
                 '(' + str(b) + '+' + str(c) + ')' +
                 ('' if j == len(right) - 1 else str(d)))

    return ans