0282. 给表达式添加运算符

ITCharge大约 3 分钟

---

0282. 给表达式添加运算符

标签：数学、字符串、回溯
难度：困难

题目链接

0282. 给表达式添加运算符 - 力扣

题目大意

描述：

给定一个仅包含数字 $0 \sim 9$ 的字符串 $num$ 和一个目标值整数 $target$ ，在 $num$ 的数字之间添加「二元」运算符（不是一元）+、- 或 *。

要求：

返回所有能够得到 $target$ 的表达式。

说明：

注意：返回表达式中的操作数不应该包含前导零。
注意：一个数字可以包含多个数位。
$1 \le num.length \le 10$ 。
$num$ 仅含数字。
$-2^{31} \le target \le 2^{31} - 1$ 。

示例：

示例 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。

解题思路

思路 1：回溯算法

使用回溯算法枚举所有可能的表达式，在每两个数字之间选择插入 +、-、* 或不切分继续拼接数位，并在构造过程中实时计算表达式值以实现剪枝。

核心思想：

状态维护：维护两个关键变量。
- $cur$ ：当前表达式已计算的值。
- $last$ ：最近一次加入表达式且尚未「结算」的乘法因子。
运算符处理：
- 加法 +x： $cur' = cur + x$ ， $last' = x$ 。
- 减法 -x： $cur' = cur - x$ ， $last' = -x$ 。
- 乘法 *x：由于乘法优先级高，需要撤回之前的 $last$ ，再计算新的值：
  $cur' = cur - last + last \times x$ ， $last' = last \times x$ 。

算法步骤：

初始化：从位置 $i = 0$ 开始，选择第一个数字作为起点。
枚举切分：从当前位置 $i$ 开始，枚举所有可能的数字段 $num[i..j]$ 。
前导零处理：如果 $num[i] = '0'$ 且 $j > i$ ，则跳过（避免前导零）。
运算符选择：
- 如果是第一个数字段，直接递归处理。
- 否则尝试三种运算符：+、-、*。
递归搜索：更新状态后递归处理剩余部分。
结果收集：当处理完所有数字且 $cur = target$ 时，记录当前表达式。

关键细节：

起始位置不能放置运算符，只能选择数字段。
前导零约束：以 '0' 开头的数字段只能取单个 '0'。
乘法优先级处理：通过维护 $last$ 变量正确处理乘法的结合性。

思路 1：代码

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        # 回溯 + 逐步结算表达式值，使用 last 处理乘法优先级
        n = len(num)
        ans = []

        def dfs(i: int, path: str, cur: int, last: int) -> None:
            # i: 当前处理到 num 的下标
            # path: 当前构造的表达式字符串
            # cur: 当前表达式已结算的值
            # last: 最近一次加入表达式、但在乘法优先级下需要与后续数相乘的因子
            if i == n:
                if cur == target:
                    ans.append(path)
                return

            # 从位置 i 开始枚举下一个操作数 num[i:j]
            # 为避免前导零，如果 num[i] == '0'，则只能取单个 '0'
            val = 0
            for j in range(i, n):
                # 前导零剪枝
                if j > i and num[i] == '0':
                    break

                # 将 num[i..j] 解析为整数 val
                val = val * 10 + (ord(num[j]) - ord('0'))
                s = num[i:j + 1]

                if i == 0:
                    # 表达式起点，不能放运算符
                    dfs(j + 1, s, val, val)
                else:
                    # 加号
                    dfs(j + 1, path + '+' + s, cur + val, val)
                    # 减号
                    dfs(j + 1, path + '-' + s, cur - val, -val)
                    # 乘号：先撤回 last，再乘 val，加回去
                    dfs(j + 1, path + '*' + s, cur - last + last * val, last * val)

        dfs(0, '', 0, 0)
        return ans

思路 1：复杂度分析

时间复杂度： $O(3^{n-1} \times n)$ 。共有 $n-1$ 个插入位，每处最多 $3$ 种运算符选择，且每次切分还包含将子串转整数与字符串拼接的 $O(n)$ 开销。
空间复杂度： $O(n)$ 。递归深度与表达式长度同阶，路径与调用栈消耗线性空间。