目录

0282:给表达式添加运算符(★★)

力扣第 282 题

题目

给定一个仅包含数字 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 仅含数字
  • -231 <= target <= 231 - 1

相似问题:

分析

#1

  • 回溯时,要递推 exp+op+num[i:j] 的值
  • 考虑将 exp 最后一个连乘式(包括负号)拆出来,变成 exp_ + mul
  • 维护 exp_ 和 mul 的值,即可递推
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        def dfs(i,s,w,mul):
            if i==n:
                if w+mul==target:
                    res.append(s)
                return
            for j in range(i,i+1 if num[i]=='0' else n):
                x = num[i:j+1]
                if not s:
                    dfs(j+1,s+x,w,int(x))
                else:
                    dfs(j+1,s+'+'+x,w+mul,int(x))
                    dfs(j+1,s+'-'+x,w+mul,-int(x))
                    dfs(j+1,s+'*'+x,w,mul*int(x))
        res = []
        n = len(num)
        dfs(0,'',0,0)
        return res

510 ms

2

  • 还可以将连乘式 mul 拆成 a * b,a 包括负号,b 是最后一个乘数
  • 即可按 num 的每一位递推

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        def dfs(i,s,w,a,b):
            if i==n:
                if w+a*b==target:
                    res.append(s)
                return
            x = num[i]
            if b:
                dfs(i+1,s+x,w,a,b*10+int(x))
            dfs(i+1,s+'+'+x,w+a*b,1,int(x))
            dfs(i+1,s+'-'+x,w+a*b,-1,int(x))
            dfs(i+1,s+'*'+x,w,a*b,int(x))
        res = []
        n = len(num)
        dfs(1,num[0],0,1,int(num[0]))
        return res

410 ms