# 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 min = 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 < min) { min = 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 min = 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 < min) { min = 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 = '' mini = 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 < mini: mini = val ans = ('' if i == 0 else str(a)) + \ '(' + str(b) + '+' + str(c) + ')' + \ ('' if j == len(right) - 1 else str(d)) return ans