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

难度: Medium

给你一个下标从 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 带符号整数范围

Submission

运行时间: 28 ms

内存: 0.0 MB

class Solution:
    def minimizeResult(self, expression: str) -> str:
        numbers=expression.split("+")
        s1=numbers[0]
        s2=numbers[1]

        n1=len(s1)
        n2=len(s2)

        res=sys.maxsize
        output=""
        for i in range(n1):
            #print(i)
            for j in range(n2):
                if i==0:
                    presign=""
                    pre=1
                    
                else:
                    presign=s1[:i]
                    pre=int(presign)

                num1=int(s1[i:])
                num2=int(s2[:j+1])
                if j==n2-1:
                    postsign=""
                    post=1
                else:
                    postsign=s2[j+1:]
                    post=int(postsign)

                cur=pre*(num1+num2)*post     
    
                if cur<=res:
                    res=cur
                    output=presign+"("+str(num1)+"+"+str(num2)+")"+postsign
        return output

Explain

此题解采用穷举法来探索所有可能的括号放置位置。首先，将表达式基于'+'符号分割为两个数字子串s1和s2。对于s1和s2的每个可能的切割点，尝试将括号放置于不同的位置，计算所得结果。例如，如果s1='247'且s2='38'，会考虑将括号放置为'(47+38)'来计算2*(47+38)。对每种情况进行计算，检查是否得到更小的结果，并更新最小结果和对应的表达式。该方法通过迭代s1和s2的所有字符，来考虑所有可能的括号位置，并计算括号内外的乘积和和。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def minimizeResult(self, expression: str) -> str:
        numbers = expression.split('+')
        s1, s2 = numbers[0], numbers[1]
        n1, n2 = len(s1), len(s2)
        res = sys.maxsize
        output = ''
        for i in range(n1):
            for j in range(n2):
                presign = s1[:i] if i != 0 else ''
                pre = int(presign) if presign else 1
                num1 = int(s1[i:])
                num2 = int(s2[:j + 1])
                postsign = s2[j + 1:] if j != n2 - 1 else ''
                post = int(postsign) if postsign else 1
                cur = pre * (num1 + num2) * post
                if cur <= res:
                    res = cur
                    output = f'{presign}({num1}+{num2}){postsign}'
        return output

Explore

在本题解中并没有明确提到特定的优化策略减少计算的总情况数。算法主要依赖于双层循环来遍历所有可能的括号位置，对每个位置进行计算。优化策略可以包括使用动态规划或者分治策略，来减少重复计算，但在题解中采用的是直接的穷举法，没有特别的优化措施。

该处理方式基于数学原则，即任何数乘以1等于其本身，这不会影响计算结果的正确性。当presign或postsign为空时，意味着括号位于表达式的开始或结束，此时不存在数字前缀或后缀，将对应的乘法因子设为1是合理的，反映了这些位置的数字在乘法操作中的中立性。

在处理大数字时，确保不溢出的方法取决于使用的编程语言。在C++或Java等语言中，可以使用长整型（如long long或BigInteger）来存储大数。此外，还可以使用模运算来防止中间结果溢出，或在每步计算后进行范围检查。在设计算法时，考虑输入大小和数据类型的限制是必要的，以避免溢出和其他数值错误。

根据题解的代码实现，算法只记录第一次找到的最小结果对应的表达式。如果后续找到相同的最小结果但表达式不同，它不会更新已存储的表达式。这种做法简化了实现，但如果需要记录所有可能的最小表达式，可以通过将结果存入列表或其他数据结构中来实现，每次找到相同的最小结果时，添加新的表达式到列表中。