#2232
Minimize Result by Adding Parentheses to Expression
specialist · 645 · lc medium +30 · verified · 68.2% accepted · 226 likes · top 75%
Description
You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> are positive integers.
Insert one pair of parentheses so that the opening parenthesis is to the left of '+' and the closing parenthesis is to the right, making the expression evaluate to the smallest possible value.
Return the modified expression. If multiple placements produce the same minimum, return any one of them.
It is guaranteed that all values fit in a signed 32-bit integer.
Example 1:
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.
Example 2:
Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
Example 3:
Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.
Code
1
2
3