Medium

题目描述

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

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

返回添加一对括号后，能够使 expression 计算得到最小值的字符串。如果存在多个答案都能得到相同的结果，返回任意一个。

题目数据保证，原始的 expression 和添加满足要求的任意一对括号之后的 expression，都能够用一个 32 位有符号整数表示。

示例 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 位有符号整数表示

解题思路

解题思路

这道题的关键是理解添加括号后的表达式形式。对于字符串 "num1+num2"，我们需要在某些位置添加括号，最终的表达式形式为：a * (b + c) * d，其中：

  • a 是 num1 的前缀部分（可能为空，此时值为 1）
  • b 是 num1 的后缀部分
  • c 是 num2 的前缀部分
  • d 是 num2 的后缀部分（可能为空，此时值为 1）

解法思路：

  1. 首先找到 '+' 的位置，将字符串分为两部分
  2. 枚举所有可能的左括号位置（在 '+' 左边）
  3. 枚举所有可能的右括号位置（在 '+' 右边）
  4. 对于每种括号放置方案，计算表达式的值
  5. 记录产生最小值的方案

具体步骤：

  • 左括号可以放在 num1 的任意位置之前（包括最开始）
  • 右括号可以放在 num2 的任意位置之后（包括最末尾）
  • 计算每种方案对应的 a * (b + c) * d 的值
  • 选择结果最小的方案

由于表达式长度最多为 10，暴力枚举的时间复杂度完全可以接受。

代码实现

class Solution {
public:
    string minimizeResult(string expression) {
        int plusPos = expression.find('+');
        string num1 = expression.substr(0, plusPos);
        string num2 = expression.substr(plusPos + 1);
        
        int minVal = INT_MAX;
        string result;
        
        // 枚举左括号位置
        for (int i = 0; i < num1.length(); i++) {
            // 枚举右括号位置
            for (int j = 1; j <= num2.length(); j++) {
                string a = i == 0 ? "1" : num1.substr(0, i);
                string b = num1.substr(i);
                string c = num2.substr(0, j);
                string d = j == num2.length() ? "1" : num2.substr(j);
                
                int val = stoi(a) * (stoi(b) + stoi(c)) * stoi(d);
                
                if (val < minVal) {
                    minVal = val;
                    result = (i == 0 ? "" : num1.substr(0, i)) + 
                            "(" + num1.substr(i) + "+" + num2.substr(0, j) + ")" +
                            (j == num2.length() ? "" : num2.substr(j));
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def minimizeResult(self, expression: str) -> str:
        plus_pos = expression.index('+')
        num1 = expression[:plus_pos]
        num2 = expression[plus_pos + 1:]
        
        min_val = float('inf')
        result = ""
        
        # 枚举左括号位置
        for i in range(len(num1)):
            # 枚举右括号位置
            for j in range(1, len(num2) + 1):
                a = 1 if i == 0 else int(num1[:i])
                b = int(num1[i:])
                c = int(num2[:j])
                d = 1 if j == len(num2) else int(num2[j:])
                
                val = a * (b + c) * d
                
                if val < min_val:
                    min_val = val
                    left_part = "" if i == 0 else num1[:i]
                    right_part = "" if j == len(num2) else num2[j:]
                    result = left_part + "(" + num1[i:] + "+" + num2[:j] + ")" + right_part
        
        return result

public class Solution {
    public string MinimizeResult(string expression) {
        int plusPos = expression.IndexOf('+');
        string num1 = expression.Substring(0, plusPos);
        string num2 = expression.Substring(plusPos + 1);
        
        int minVal = int.MaxValue;
        string result = "";
        
        // 枚举左括号位置
        for (int i = 0; i < num1.Length; i++) {
            // 枚举右括号位置
            for (int j = 1; j <= num2.Length; j++) {
                int a = i == 0 ? 1 : int.Parse(num1.Substring(0, i));
                int b = int.Parse(num1.Substring(i));
                int c = int.Parse(num2.Substring(0, j));
                int d = j == num2.Length ? 1 : int.Parse(num2.Substring(j));
                
                int val = a * (b + c) * d;
                
                if (val < minVal) {
                    minVal = val;
                    string leftPart = i == 0 ? "" : num1.Substring(0, i);
                    string rightPart = j == num2.Length ? "" : num2.Substring(j);
                    result = leftPart + "(" + num1.Substring(i) + "+" + num2.Substring(0, j) + ")" + rightPart;
                }
            }
        }
        
        return result;
    }
}

var minimizeResult = function(expression) {
    const plusIndex = expression.indexOf('+');
    let minValue = Infinity;
    let result = '';
    
    for (let i = 0; i < plusIndex; i++) {
        for (let j = plusIndex + 2; j <= expression.length; j++) {
            const left1 = expression.substring(0, i) || '1';
            const left2 = expression.substring(i, plusIndex);
            const right1 = expression.substring(plusIndex + 1, j);
            const right2 = expression.substring(j) || '1';
            
            const value = parseInt(left1) * (parseInt(left2) + parseInt(right1)) * parseInt(right2);
            
            if (value < minValue) {
                minValue = value;
                result = left1 === '1' ? `(${left2}+${right1})${right2 === '1' ? '' : right2}` :
                        right2 === '1' ? `${left1}(${left2}+${right1})` :
                        `${left1}(${left2}+${right1})${right2}`;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)其中 n 是表达式长度，需要枚举所有可能的括号位置组合
空间复杂度O(1)只使用常数额外空间存储临时变量

相关题目