0282. Expression Add Operators¶
题目信息¶
- 题号:
0282
- 难度:
Hard
- 主题:
数字字符串、表达式、运算符插入、结果枚举
- 原题:
- 重点:
数字顺序不能改变、可插入
+-*或直接拼接、乘法优先级、操作数前导零限制
题目重述¶
给定只包含十进制数字的字符串 num 和整数 target,在相邻数字之间选择插入 +、-、*,或者不插入运算符以把数字拼成同一个操作数。返回所有计算结果恰好等于 target 的表达式字符串。
num 的长度位于 [1, 10],target 位于 32 位有符号整数范围。表达式必须保持原数字的顺序,并使用通常的运算优先级:乘法先于加减法,不使用括号。多位操作数不能以 0 开头,单独的 0 合法;例如可以使用 0,不能使用 04。结果顺序不限,所有满足条件的表达式都应返回。
自建示例¶
同一输入存在多种合法表达式:
输入:num = "222",target = 6
输出:["2+2+2", "2*2+2", "2+2*2"]
解释:三种表达式都保持数字顺序并得到 6;乘法按照标准优先级先计算。输出顺序可以不同。
前导零限制会排除某些分段:
输入:num = "204",target = 2
输出:["2+0*4", "2-0*4"]
解释:两式的结果都是 2。把后两位组成操作数 04 不合法,因为多位操作数不能以 0 开头。
回溯并维护乘法最后一项¶
从左到右决定每一段数字的结束位置。每次可以把当前数字片段接在已有表达式后,
并选择 +、- 或 *;首个片段不添加运算符。若片段以 0 开头且长度超过 1,
立即停止继续延长,保留单独的 0 仍然合法。
为了在没有括号的表达式中正确处理乘法,递归状态除了当前值 value,还保存最后一项 last:
加法后的新值为
value + operand,最后一项变为operand;减法后的新值为
value - operand,最后一项变为-operand;乘法要撤销旧的最后一项,再加入乘积:
value - last + last * operand。
例如当前表达式值为 2+3 时,value=5,last=3;追加 *4 后改成
5-3+12=14,等价于按乘法优先级计算 2+3*4。
正确性说明¶
回溯枚举每个可能的数字分段,前导零剪枝只排除题目禁止的操作数。状态中的 value 是当前表达式按通常优先级
求值后的结果,last 是仍可能被下一个乘法吸收的最后加减项;三种转移分别保持这一语义。
当游标到达字符串末尾时,若 value==target,当前表达式合法且应加入答案;所有合法分段和运算符选择都被枚举,
所以没有遗漏或伪结果。
C++ 实现¶
class Solution {
void search(const std::string& num, long long target, int position,
long long value, long long last, std::string& expression,
std::vector<std::string>& answer) {
if (position == static_cast<int>(num.size())) {
if (value == target) answer.push_back(expression);
return;
}
const std::size_t old_size = expression.size();
long long operand = 0;
for (int end = position; end < static_cast<int>(num.size()); ++end) {
if (end > position && num[position] == '0') break;
operand = operand * 10 + (num[end] - '0');
const std::string token = num.substr(position, end - position + 1);
if (position == 0) {
expression += token;
search(num, target, end + 1, operand, operand,
expression, answer);
expression.resize(old_size);
continue;
}
expression += '+';
expression += token;
search(num, target, end + 1, value + operand, operand,
expression, answer);
expression.resize(old_size);
expression += '-';
expression += token;
search(num, target, end + 1, value - operand, -operand,
expression, answer);
expression.resize(old_size);
expression += '*';
expression += token;
search(num, target, end + 1,
value - last + last * operand, last * operand,
expression, answer);
expression.resize(old_size);
}
}
public:
std::vector<std::string> addOperators(const std::string& num,
int target) {
std::vector<std::string> answer;
std::string expression;
search(num, target, 0, 0, 0, expression, answer);
return answer;
}
};
代码分析¶
num 长度最多为 10,回溯的主要规模来自切分点和三种运算符组合;结果数量本身也可能指数级,
因此不能把枚举问题声称为线性。表达式字符串使用回溯复用一份缓冲区,递归深度最多为 O(|num|);
数值状态使用 long long 保存中间乘积,避免窄整数在比较目标前溢出。