2232. Minimize Result by Adding Parentheses to Expression LeetCode Solution
In this guide, you will get 2232. Minimize Result by Adding Parentheses to Expression LeetCode Solution with the best time and space complexity. The solution to Minimize Result by Adding Parentheses to Expression problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimize Result by Adding Parentheses to Expression
You are given a 0-indexed string expression of the form “+” where and 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 the smallest possible value. The left parenthesis must be added to the left of ‘+’ and the right parenthesis must be added to the right of ‘+’.
Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.
The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Input: expression = “247+38”
Output: “2(47+38)”
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that “2(4)7+38” is invalid because the right parenthesis must be to the right of the ‘+’.
It can be shown that 170 is the smallest possible value.
Input: expression = “999+999”
Output: “(999+999)”
Explanation: The expression evaluates to 999 + 999 = 1998.
Constraints:
3 <= expression.length <= 10
expression consists of digits from '1' to '9' and '+'.
expression starts and ends with digits.
expression contains exactly one '+'.
The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Complexity Analysis
Time Complexity: O((\log n)^4)
Space Complexity: O(1)
2232. Minimize Result by Adding Parentheses to Expression LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
2232. Minimize Result by Adding Parentheses to Expression LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
2232. Minimize Result by Adding Parentheses to Expression LeetCode Solution in Python
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 # code by PROGIEZ
