LeetCode 题解工作台
给表达式添加运算符
给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元） + 、 - 或 * ，返回 所有 能够得到 target 的表达式。 注意，返回表达式中的操作数 不应该 包含前导零。 注意 ，一个数字可以包含多个数位。 示例 1:…
3
题型
3
代码语言
3
相关题
当前训练重点
困难 · 回溯·pruning
答案摘要
class Solution: def addOperators(self, num: str, target: int) -> List[str]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回 所有 能够得到 target 的表达式。
注意，返回表达式中的操作数 不应该 包含前导零。
注意，一个数字可以包含多个数位。
示例 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。
示例 3:
输入: num = "3456237490", target = 9191
输出: []
解释: 表达式 “3456237490” 无法得到 9191 。
提示：
1 <= num.length <= 10num仅含数字-231 <= target <= 231 - 1
解题思路
方法一
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
ans = []
def dfs(u, prev, curr, path):
if u == len(num):
if curr == target:
ans.append(path)
return
for i in range(u, len(num)):
if i != u and num[u] == '0':
break
next = int(num[u : i + 1])
if u == 0:
dfs(i + 1, next, next, path + str(next))
else:
dfs(i + 1, next, curr + next, path + "+" + str(next))
dfs(i + 1, -next, curr - next, path + "-" + str(next))
dfs(
i + 1,
prev * next,
curr - prev + prev * next,
path + "*" + str(next),
)
dfs(0, 0, 0, "")
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | * At every step along the way, we consider exactly 4 different choices or 4 different recursive paths |
| 空间 | * For both Python and Java implementations we have a list data structure that we update on the fly and only for valid expressions do we create a new string and add to our `answers` array |
面试官常问的追问
外企场景- question_mark
They emphasize that a number can contain multiple digits, which is a hint to iterate over every substring as the next operand.
- question_mark
They ask how to handle multiplication without evaluating the whole string each time, which points to tracking the previous operand.
- question_mark
They mention leading zeros or bring up inputs like "105", which is a signal that pruning invalid operands matters.
常见陷阱
外企场景- error
Treating every digit as a separate operand and missing valid expressions such as "12-3".
- error
Evaluating left to right and getting multiplication wrong because "*" must adjust the previous term, not just append to the total.
- error
Allowing operands like "00" or "05", which creates invalid expressions even when the arithmetic matches target.
进阶变体
外企场景- arrow_right_alt
Return only the count of valid expressions instead of the full list, which keeps the same backtracking structure but changes output handling.
- arrow_right_alt
Allow division or parentheses, which breaks the simple previous-operand trick and requires a different expression-state model.
- arrow_right_alt
Restrict operators to only "+" and "-", which removes precedence handling and makes state management much simpler.