# 题目: 282. 给表达式添加运算符
给定一个仅包含数字 0-9
的字符串 num
和一个目标值整数 target
,在 num
的数字之间添加 二元 运算符(不是一元)+
、-
或 *
,返回所有能够得到目标值的表达式。
# 示例1:
输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]
# 示例2:
输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]
# 题解: 回溯模拟
根据题目,在目标字符串 num 中,每一个空隙随意的插入四个符号 *
,-
,+
,''
中的一个。
可以使用用「回溯法」来模拟这个过程。
从左向右构建表达式,并实时计算表达式的结果。由于乘法运算优先级高于加法和减法运算,我们还需要保存最后一个连乘串(如 234)的运算结果。
定义一个递归函数用于回溯:
- expr 为当前构建的表达式
- i 表示当前枚举到的字符串的第 i 个数字
- res 为当前表达式计算的结果
- mul 为表达式最后一个连乘串的计算结果。
关于递归函数的终止
- i === n 的时候,表明字符串已经构建完毕,此时以 res === target 为判断构建字符串是否符合标准
- i < n 的时候,对字符串添加一个操作符
- 若 添加 + 号
- 若 添加 - 号
- 如 添加 * 号