6038. 向表达式添加括号后的最小结果

执行用时：6 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：40.1 MB, 在所有 Java 提交中击败了100.00% 的用户
通过测试用例：124 / 124

题目链接：https://leetcode-cn.com/problems/minimize-result-by-adding-parentheses-to-expression/

class Solution {
    public String minimizeResult(String expression) {
        int plus = expression.lastIndexOf("+");
        int m = expression.substring(0, plus)
                .toCharArray()
                .length;
        int n = expression.substring(plus + 1)
                .toCharArray()
                .length;
        int minNum = Integer.MAX_VALUE;
        int end = expression.length();
        int left = 0, right = end;
        for (int i = 0; i < m; i++) {
            for (int j = end; j > plus + 1; j--) {
                int a = (i > 0 ? Integer.parseInt(expression.substring(0, i)) : 1);
                int b = Integer.parseInt(expression.substring(i, m));
                int c = Integer.parseInt(expression.substring(plus+1, j));
                int d = (j < end ? Integer.parseInt(expression.substring(j, end)) : 1);
                int sum = a * (b + c) * d;
                if (sum < minNum) {
                    minNum = sum;
                    left = i;
                    right = j;
                }
            }
        }
        String res = expression.substring(0,left) + "("
                + expression.substring(left, right) + ")"
                + expression.substring(right) ;
        return res;
    }
}