给表达式添加运算符

[编程题]给表达式添加运算符

热度指数：1143 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：字符串长度满足 $1 \le n \le 10 \$ ， nums 中仅包含数字， $|target| \le 10^9 \$

示例1

输入

"123",6

输出

["1+2+3","1*2*3"]

示例2

输入

"00",0

输出

["0+0","0*0","0-0"]

算法知识视频讲解

Python3

E-Doz

class Solution:
    def addOpt(self , num: str, target: int) -> List[str]:
        # write code here
        def dfs(num, target,stack, cur, ret):
            if not num:
                if sum(stack) == target:
                    ret.append(cur)
                return
            for i in range(len(num)):
                if i > 0 and num[i] == "0":
                    return
                n = int(num[:i+1])
                dfs(num[i+1:], target, stack+[n], cur+"+"+str(n), ret)
                dfs(num[i+1:], target, stack+[-n], cur+"-"+str(n), ret)
                temp = stack[-1]
                dfs(num[i+1:], target, stack[:-1]+[temp*n],cur+"*"+str(n),ret)
        ret = []
        s = ""
        for i in range(len(num)):
            if i > 0 and num[i] == "0":
                break
            n = int(num[:i+1])
            dfs(num[i+1:], target, [n], str(n), ret)
        return ret

发表于 2022-10-03 20:51:42 回复(0)