给表达式添加运算符

难度: Hard

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加二元运算符（不是一元）+、- 或 * ，返回所有能够得到 target 的表达式。

注意，返回表达式中的操作数 不应该 包含前导零。

示例 1:

输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"] 
解释: “1*2*3” 和 “1+2+3” 的值都是6。

示例 2:

输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]
解释: “2*3+2” 和 “2+3*2” 的值都是8。

示例 3:

输入: num = "3456237490", target = 9191
输出: []
解释: 表达式 “3456237490” 无法得到 9191 。

提示：

1 <= num.length <= 10
num 仅含数字
-2³¹ <= target <= 2³¹ - 1

Submission

运行时间: 363 ms

内存: 16.4 MB

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        n = len(num)
        ret = []
        def helper(expr,i,res,mul):
            if i==n:
                if res == target:
                    ret.append(''.join(expr))
                return 
            signIdx = len(expr)
            if i>0:
                expr.append('')
            val = 0
            for j in range(i,n):
                if j>i and num[i]=='0': break
                val = val*10 + int(num[j])
                expr.append(num[j])
                if i==0:
                    helper(expr,j+1,val,val)
                else:
                    expr[signIdx] = '+'
                    helper(expr,j+1,res+val,val)
                    expr[signIdx] = '-'
                    helper(expr,j+1,res-val,-val)
                    expr[signIdx] = '*'
                    helper(expr,j+1,res-mul+mul*val,mul*val)
            del expr[signIdx:]
        helper([],0,0,0)
        return ret

Explain

该题解使用回溯法，采用深度优先搜索的思路，递归地在数字字符串的每个位置尝试添加不同的运算符（+、- 或 *），生成所有可能的表达式，并在表达式结果等于目标值时加入结果列表。在递归过程中，通过维护当前的计算结果 res 和上一次乘法的值 mul，可以在添加新运算符时，根据上一次的操作符进行相应的计算。

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

空间复杂度: O(n) + O(4^n)

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        n = len(num)
        ret = []
        
        def helper(expr, i, res, mul):
            if i == n:
                # 当处理完所有数字后，如果结果等于目标值，则将当前表达式加入结果列表
                if res == target:
                    ret.append(''.join(expr))
                return
            
            signIdx = len(expr)
            if i > 0:
                expr.append('')  # 在表达式中添加一个占位符，用于存储运算符
            
            val = 0
            for j in range(i, n):
                if j > i and num[i] == '0':
                    break  # 如果当前数字为 0，且不是单独的 0，则不继续处理
                
                val = val * 10 + int(num[j])  # 计算当前处理的数字
                expr.append(num[j])  # 将数字添加到表达式中
                
                if i == 0:
                    # 如果是第一个数字，不需要添加运算符，直接递归处理下一个数字
                    helper(expr, j + 1, val, val)
                else:
                    # 尝试添加不同的运算符
                    expr[signIdx] = '+'
                    helper(expr, j + 1, res + val, val)
                    
                    expr[signIdx] = '-'
                    helper(expr, j + 1, res - val, -val)
                    
                    expr[signIdx] = '*'
                    helper(expr, j + 1, res - mul + mul * val, mul * val)
            
            del expr[signIdx:]  # 回溯，删除当前处理的数字和运算符
        
        helper([], 0, 0, 0)
        return ret

Explore

在`helper`函数中，表达式`res - mul + mul * val`用于处理乘号`*`的运算。这里的逻辑是首先撤销上一次运算的结果，然后将上一次的结果与当前数字`val`进行乘法运算。例如，如果表达式是`a+b*c`，在递归中，当处理到`b`时，`res`是`a+b`，`mul`是`b`。接下来要处理`c`，我们首先从`res`中减去`mul`（即减去`b`），然后再加上`b*c`，这样更新的`res`就是`a+b*c`的结果。这种方法允许我们在不维护表达式的具体结构的情况下，正确地处理乘法运算的优先级。

如果输入的数字字符串`num`非常长，递归回溯方法的执行时间和空间消耗将会显著增加，因为算法需要枚举所有可能的运算符插入方式，其时间复杂度大约为`O(3^n)`，其中`n`是数字的长度。这可能导致在极端情况下执行时间过长（超时）或递归调用层数过多而引起栈溢出。在实际应用中，通常需要对输入的长度或递归的深度有一定的限制，以防止这种情况发生。

题解中的这个规则是为了防止数字以`0`开头，除非`0`是单独的一个数字。例如，`105`和`205`中的`0`并不单独，而是数字的一部分，因此可以正常处理。但是，如果数字如`010`或`005`，则应该避免生成以`0`开头的多位数。具体到`105`或`205`，算法将正常处理`1`和`2`，然后继续处理后面的数字，不会中断处理。

这样设计的原因是表达式的开始不能有运算符，第一个数字前面没有其他数字或运算符，因此直接将第一个数字作为开始的部分，并递归处理后续的数字和运算符。这不仅符合数学表达式的规则，也简化了逻辑处理，避免在表达式开始就处理不必要的运算符插入逻辑。