0282. Expression Add Operators ============================== 题目信息 -------- :题号: 0282 :难度: Hard :主题: 数字字符串、表达式、运算符插入、结果枚举 :原题: `LeetCode 0282 `_ :重点: 数字顺序不能改变、可插入 ``+`` ``-`` ``*`` 或直接拼接、乘法优先级、操作数前导零限制 题目重述 -------- 给定只包含十进制数字的字符串 ``num`` 和整数 ``target``,在相邻数字之间选择插入 ``+``、``-``、``*``,或者不插入运算符以把数字拼成同一个操作数。返回所有计算结果恰好等于 ``target`` 的表达式字符串。 ``num`` 的长度位于 ``[1, 10]``,``target`` 位于 32 位有符号整数范围。表达式必须保持原数字的顺序,并使用通常的运算优先级:乘法先于加减法,不使用括号。多位操作数不能以 ``0`` 开头,单独的 ``0`` 合法;例如可以使用 ``0``,不能使用 ``04``。结果顺序不限,所有满足条件的表达式都应返回。 自建示例 -------- 同一输入存在多种合法表达式: .. code-block:: text 输入:num = "222",target = 6 输出:["2+2+2", "2*2+2", "2+2*2"] 解释:三种表达式都保持数字顺序并得到 6;乘法按照标准优先级先计算。输出顺序可以不同。 前导零限制会排除某些分段: .. code-block:: text 输入: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++ 实现 -------- .. code-block:: cpp class Solution { void search(const std::string& num, long long target, int position, long long value, long long last, std::string& expression, std::vector& answer) { if (position == static_cast(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(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 addOperators(const std::string& num, int target) { std::vector answer; std::string expression; search(num, target, 0, 0, 0, expression, answer); return answer; } }; 代码分析 -------- ``num`` 长度最多为 10,回溯的主要规模来自切分点和三种运算符组合;结果数量本身也可能指数级, 因此不能把枚举问题声称为线性。表达式字符串使用回溯复用一份缓冲区,递归深度最多为 ``O(|num|)``; 数值状态使用 ``long long`` 保存中间乘积,避免窄整数在比较目标前溢出。