0282：给表达式添加运算符（★★）

2015-10-09 约 450 字预计阅读 1 分钟次阅读

力扣第 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 仅含数字
-2³¹ <= target <= 2³¹ - 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

目录

0282：给表达式添加运算符（★★）

题目

分析

#1

2

解答