中等

问题描述

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2

示例 2：

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

提示：

• 1 <= expression.length <= 20
• expression 由数字和算符 '+'、'-' 和 '*' 组成。
• 输入表达式中的所有整数值在范围 [0, 99]

分治

对于一个算式 $\text x\;op\;\text y$，它的结果组合取决于 $\text x$ 和 $\text y$ 的结果组合。遍历算式字符串，按照运算符将算式拆分成左子算式与右子算式，递归计算左子算式与右子算式的结果组合，最终得到整个算式结果的组合数。

/**
 * @param {string} expression
 * @return {number[]}
 */
var diffWaysToCompute = function (expression) {
  const ans = []
  const n = expression.length
  for (let i = 0; i < n; i++) {
    const op = expression[i]
    if (['+', '-', '*'].includes(op)) {
      const left = diffWaysToCompute(expression.substring(0, i))
      const right = diffWaysToCompute(expression.substring(i + 1))
      for (const l of left) {
        for (const r of right) {
          if (op === '*') ans.push(l * r)
          if (op === '+') ans.push(l + r)
          if (op === '-') ans.push(l - r)
        }
      }
    }
  }
  if (ans.length === 0) ans.push(+expression)
  return ans
}

• 时间复杂度：$O(C_{n})$。复杂度与最终结果数相关，最终结果数为「卡特兰数」。
• 空间复杂度：$O(C_{n})$。复杂度与最终结果数相关，最终结果数为「卡特兰数」。

动态规划

设定 $dp[l][r]$ ($l \leq r$)为算式中第 $l$ 个数到第 $r$ 个数的结果组合，在 $l$ 到 $r$ 范围内，枚举左子算式与右子算式组合（枚举方式与分治方法类似），并计算结果组合，最终 $dp[0][n-1]$ 即为答案。

/**
 * @param {string} expression
 * @return {number[]}
 */
var diffWaysToCompute = function (expression) {
  const ops = []
  const nums = []
  for (let i = 0, j = 0; j < expression.length; j++) {
    const e = expression[j]
    if (['+', '-', '*'].includes(e)) {
      ops.push(e)
      nums.push(+expression.substring(i, j))
      i = j + 1
    }
    if (j === expression.length - 1) nums.push(+expression.substring(i))
  }
  const n = nums.length
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => []))
  for (let r = 0; r < n; r++) {
    for (let l = r; l > -1; l--) {
      if (l === r) {
        dp[l][r].push(nums[l])
      } else {
        for (let i = 0; i < r - l; i++) {
          for (const right of dp[r - i][r]) {
            for (const left of dp[l][r - i - 1]) {
              const op = ops[r - i - 1]
              if (op === '*') dp[l][r].push(left * right)
              if (op === '+') dp[l][r].push(left + right)
              if (op === '-') dp[l][r].push(left - right)
            }
          }
        }
      }
    }
  }
  return dp[0][n - 1]
}

• 时间复杂度：$O(C_{n})$。复杂度与最终结果数相关，最终结果数为「卡特兰数」。
• 空间复杂度：$O(C_{n})$。复杂度与最终结果数相关，最终结果数为「卡特兰数」。