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

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

1 <= num.length <= 10
num 仅含数字
-2 ** 31 <= target <= 2 ** 31 - 1

思路

  1. 回溯，深度优先搜索
  2. 粗暴解决方案：遍历每一个可能存在的表达式，通过 eval 进行计算，匹配 target 的表达式加入到结果中
  3. 将字符串视为由个位数组成的数组，前后两数的结合方式有 * + - 以及直接拼接（特殊情况：前数若为 0 则不可进行拼接操作）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var addOperators = function (num, target) {
  const result = []
  const handler = (curVals, nextIndex) => {
    if (nextIndex >= num.length) {
      const expression = curVals.join('')
      if (eval(expression) === target) {
        result.push(expression)
      }
      return
    }
    const nextVal = num[nextIndex]
    ++nextIndex
    handler([...curVals, '+', nextVal], nextIndex)
    handler([...curVals, '-', nextVal], nextIndex)
    handler([...curVals, '*', nextVal], nextIndex)
    if (curVals[curVals.length - 1] !== '0') {
      curVals[curVals.length - 1] = `${curVals[curVals.length - 1]}${nextVal}`
      handler(curVals, nextIndex)
    }
  }
  handler([num[0]], 1)
  return result
}

优化方案

  • 使用 eval 进行表达式计算，虽然取巧，但性能较差
  • 可以在递归过程将部分计算结果向下传递，进而避免子表达式的反复计算
  • 考虑到乘法的优先级高于加减法，左右拼接的优先级高于乘法，递归时需要传递多个参数 factor1, factor2, factor3，当前代数式结果 curResult = factor1 + factor2 * factor3
  • [factor1, factor2, factor3] 初始值为 [0, 1, vals[0]]
  • 加法运算时，[factor1, factor2, factor3] 迭代为 [curResult, 1, nextVal]
  • 减法运算时，[factor1, factor2, factor3] 迭代为 [curResult, -1, nextVal]
  • 乘法运算时，[factor1, factor2, factor3] 迭代为 [factor1, factor2 * factor3, nextVal]
  • 结合计算时，[factor1, factor2, factor3] 迭代为 [factor1, factor2 * factor3, factor3 * 10 + nextVal]
  • 使用 number 数组 vals 取代 num 字符串以便代数计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var addOperators = function (num, target) {
  const vals = num.split('').map((item) => Number(item))
  const result = []
  const handler = (curVals, nextIndex, factor1, factor2, factor3) => {
    const curResult = factor1 + factor2 * factor3
    if (nextIndex >= vals.length) {
      if (curResult === target) {
        result.push(curVals.join(''))
      }
      return
    }
    const nextVal = vals[nextIndex]
    ++nextIndex
    handler([...curVals, '+', nextVal], nextIndex, curResult, 1, nextVal)
    handler([...curVals, '-', nextVal], nextIndex, curResult, -1, nextVal)
    handler([...curVals, '*', nextVal], nextIndex, factor1, factor2 * factor3, nextVal)
    if (factor3 !== 0) {
      factor3 = factor3 * 10 + nextVal
      curVals[curVals.length - 1] = factor3
      handler(curVals, nextIndex, factor1, factor2, factor3)
    }
  }
  handler([vals[0]], 1, 0, 1, vals[0])
  return result
}