2232. 向表达式添加括号后的最小结果 - 《算法》

题目
思路
代码

题目

给你一个下标从 0 开始的字符串 expression ，格式为 "<num1>+<num2>" ，其中 <num1> 和 <num2> 表示正整数。

请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到最小可能值。左括号必须添加在 '+' 的左侧，而右括号必须添加在 '+' 的右侧。

返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到最小可能值。如果存在多个答案都能产生相同结果，返回任意一个答案。

生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。

示例 1： 输入：expression = “247+38” 输出：”2(47+38)” 解释：表达式计算得到 2 (47 + 38) = 2 85 = 170 。注意 “2(4)7+38” 不是有效的结果，因为右括号必须添加在 ‘+’ 的右侧。可以证明 170 是最小可能值。

示例 2： 输入：expression = “12+34” 输出：”1(2+3)4” 解释：表达式计算得到 1 (2 + 3) 4 = 1 5 4 = 20 。

示例 3： 输入：expression = “999+999” 输出：”(999+999)” 解释：表达式计算得到 999 + 999 = 1998 。

提示：

3 <= expression.length <= 10
expression 仅由数字 '1' 到 '9' 和 '+' 组成
expression 由数字开始和结束
expression 恰好仅含有一个 '+'.
expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围

思路

暴力枚举「括号内左边加数的最高位下标」和「括号内右边加数的最低位下标」，计算最小的乘积，返回对应的字符串即可。

主要的难点在于下标的确定和字符串的处理。

代码

class Solution {
    public String minimizeResult(String expression) {
        int n = expression.length();
        int k = expression.indexOf('+');
        int minProduct = Integer.MAX_VALUE;
        String ans = "";
        // 枚举括号内左边加数的最高位下标，最少要有一个数，因此i最大取k-1
        for (int i = 0; i <= k - 1; i++) {
            // 枚举括号内右边加数的最低位下标，最少要有一个数，因此j最小取k+1
            for (int j = k + 1; j < n; j++) {
                int cur = 1;
                // 括号内左边加数
                int a = Integer.parseInt(expression.substring(i, k));
                // 括号内右边加数
                int b = Integer.parseInt(expression.substring(k + 1, j + 1));
                // 左括号左边的数，如果左边没有数，赋值为1，右边同理
                int left = i == 0 ? 1 : Integer.parseInt(expression.substring(0, i));
                // 右括号右边的数
                int right = j + 1 == n ? 1 : Integer.parseInt(expression.substring(j + 1, n));
                if ((a + b) * left * right < minProduct) {
                    minProduct = (a + b) * left * right;
                    ans = (i == 0 ? "" : left) + "(" + a + "+" + b + ")" + (j + 1 == n ? "" : right);
                }
            }
        }
        return ans;
    }
}