LeetCode 282. 给表达式添加运算符
题目描述
原题：282. 给表达式添加运算符。
在数字串的相邻数字之间选择拼接，或插入+、-、*，返回值等于target的所有表达式。数字不能有多余前导零，运算遵循乘法优先。
示例 1：
输入：num = "123", target = 6
输出：["1+2+3","1*2*3"]
解释：两条表达式的计算结果均为 6，数字相对顺序保持不变。
提示：
- 输入为十进制数字字符串；只能插入 +、-、* 或拼接相邻数字。操作数不得有多余前导零，乘法优先于加减法。
题意分析
保持数字串的原始顺序，在相邻数字之间选择不插入运算符，或插入
+、-、*，返回所有计算结果等于target的表达式。每个数字都必须使用，不能重新排列或加入括号。连续拼接的数字组成一个操作数，多位操作数不能有前导零，但单独的
0合法。表达式按乘法优先于加减计算，不能简单地把所有运算从左到右累计。
解法：回溯切分数字并维护最后乘法项
核心思路
[!blue]
从当前未使用的位置
pos开始，枚举下一个操作数的结束位置，决定拼接多少位；第一段直接作为表达式开头，之后每一段分别尝试加、减、乘。每种表达式都有确定的操作数分段和段间运算符，这样的枚举能覆盖全部合法选择。递归除了保存表达式文本，还维护当前总值
value和最后一个带符号乘法项last。last不是简单的最后一个数字，而是最后一整段连续乘法已经贡献的值，包含它前面的正负号。接上加法时，新项就是
operand，因此更新为value + operand，并令last = operand；接上减法时，新项为-operand，更新总值并把负号保存在last中。接上乘法时，应该只扩大最后一项，而不是把整个前缀相乘。因为原总值可以写成“前面已经完成的项 + last”，先撤销旧贡献，再加入新贡献即可：
newValue = value - last + last * operand，同时把last更新成last * operand。这个替换也能继续处理一串乘法，或减号后面的乘法链，无需为每个候选另写表达式解析器。枚举操作数时逐位累积数值。若段首为
0，只允许取这一位，后续更长前缀全部非法，可以直接停止本轮延长。每次递归都推进到下一未使用位置；用完全部数字时才判断总值，等于目标就保存文本，否则结束该分支。
解题步骤
- 从位置
0、空表达式开始，逐步枚举下一段数字，使用 64 位变量保存操作数及累计结果。- 段首为零时只保留单字符零，其余情况按十进制逐位扩大操作数。
- 第一段不加运算符，直接初始化
value和last。- 后续段分别尝试加、减、乘；加减开始新项，乘法用撤销旧末项再加入新乘积的公式更新。
- 每次递归从该操作数末尾之后继续；全部字符用完且总值等于目标时加入答案。
代码实现
class Solution {
public List<String> addOperators(String num, int target) {
List<String> result = new ArrayList<>();
if (!num.isEmpty()) {
dfs(num, target, 0, 0, 0, "", result);
}
return result;
}
private void dfs(
String s,
long target,
int pos,
long value,
long last,
String expression,
List<String> result) {
if (pos == s.length()) {
if (value == target) {
result.add(expression);
}
return;
}
long operand = 0;
for (int end = pos; end < s.length(); end++) {
if (end > pos && s.charAt(pos) == '0') {
break;
}
operand = operand * 10 + s.charAt(end) - '0';
String token = s.substring(pos, end + 1);
if (pos == 0) {
dfs(s, target, end + 1, operand, operand, token, result);
} else {
dfs(s, target, end + 1, value + operand, operand, expression + "+" + token, result);
dfs(
s,
target,
end + 1,
value - operand,
-operand,
expression + "-" + token,
result);
dfs(
s,
target,
end + 1,
value - last + last * operand,
last * operand,
expression + "*" + token,
result);
}
}
}
}
func addOperators(num string, target int) []string {
result := []string{}
var dfs func(int, int64, int64, string)
dfs = func(pos int, value, last int64, expression string) {
if pos == len(num) {
if value == int64(target) {
result = append(result, expression)
}
return
}
operand := int64(0)
for end := pos; end < len(num); end++ {
if end > pos && num[pos] == '0' {
break
}
operand = operand*10 + int64(num[end]-'0')
token := num[pos : end+1]
if pos == 0 {
dfs(end+1, operand, operand, token)
} else {
dfs(end+1, value+operand, operand, expression+"+"+token)
dfs(end+1, value-operand, -operand, expression+"-"+token)
dfs(end+1, value-last+last*operand, last*operand, expression+"*"+token)
}
}
}
if len(num) > 0 {
dfs(0, 0, 0, "")
}
return result
}
复杂度分析
设数字串长度为
n，所有返回表达式的字符总量为S。
- 时间复杂度：$O(n\cdot4^n)$ 上界，每个数字间隙最多选择拼接或三个运算符，当前实现的子串与表达式拼接还包含线性字符处理成本。
- 空间复杂度：不计答案为 $O(n^2)$ 上界。递归深度为 $O(n)$，当前调用链上的多个不可变表达式前缀同时保留；返回结果另占 $O(S)$。原题
n <= 10，64 位整数足以保存这里的操作数和中间运算。
关键点总结
[!green]
- 切分数字决定操作数，选择符号决定运算，两层枚举完整覆盖表达式。
last是带符号的末尾乘法项，保留它才能在追加乘法时只修正该项贡献。- 前导零限制作用于每个操作数，单独的零不需要禁止。
- 文本用于返回答案，数值状态用于直接判定结果，二者同步构造。
易错点总结
[!yellow]
- 乘法直接计算
value * operand，会把前面其他加减项也一起相乘。- 减法后仍把
last设为正数，下一次乘法就会撤销错误符号的贡献。- 连乘后不更新
last，再追加乘法时只能回退其中一部分。- 在第一个操作数之前添加符号，会生成题目未要求的带前置运算符表达式。
- 允许以零开头的多位操作数，或把单独零也排除，都会改变合法候选集合。
- 用 32 位变量保存拼接出的操作数或中间值，即使目标参数是
int，中途结果也可能超出它的范围。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 93. 复原 IP 地址 | 中等 | 同样按位置切分数字并排除多位前导零，本题再为分段之间选择运算符。 |
| 227. 基本计算器 II | 中等 | 都需要处理乘法优先级；本题在生成表达式时回退最后一项，无需每次重新解析整串。 |