江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第282题：给表达式添加运算符

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 ，返回所有能够得到目标值的表达式。 注意： - 返回的表达式中，操作符 +、- 和 的优先级遵循正常的数学运算规则。 - 不能用括号改变运算符的优先级。 - 不能有前导零，但 0 本身是允许的。

📖 文章摘要

本文详细解析LeetCode第282题“给表达式添加运算符”，这是一道考察回溯算法和表达式计算的困难题目。文章提供了回溯法的详细实现，包含C#、Python、C++三种语言实现，配有详细的状态转移分析和性能对比。适合想要提升算法设计能力的开发者。

核心知识点： 回溯算法、表达式计算、字符串处理
难度等级： 困难
推荐人群： 具备基础算法知识，想要提升复杂问题解决能力的开发者

题目描述

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

注意：

  • 返回的表达式中，操作符 +、- 和 * 的优先级遵循正常的数学运算规则。
  • 不能用括号改变运算符的优先级。
  • 不能有前导零，但 0 本身是允许的。

示例

示例 1：

输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]
解释: "1+2+3" = 6
     "1*2*3" = 6

示例 2：

输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]
解释: "2*3+2" = 8
     "2+3*2" = 8

示例 3：

输入: num = "3456237490", target = 9191
输出: []
解释: 没有可能的表达式得到目标值

提示

  • 1 <= num.length <= 10
  • num 仅含数字
  • -2^31 <= target <= 2^31 - 1

解题思路

本题使用回溯算法求解，主要难点在于处理乘法的优先级：

  1. 基本思路：

    • 使用回溯法遍历所有可能的运算符组合
    • 对于每个数字，可以选择加号、减号或乘号
    • 需要特别处理前导零的情况

  2. 关键点：

    • 维护当前计算结果和上一个乘数
    • 乘法需要先减去上一个结果，再乘以当前数
    • 处理前导零和数字长度限制

图解思路

回溯过程状态分析表

当前位置 当前数字 运算符 当前结果 上一个数 表达式
0 1 无 1 1 “1”
1 2 + 3 2 “1+2”
2 3 + 6 3 “1+2+3”
1 2 * 2 2 “1*2”
2 3 * 6 6 “123”

运算符优先级处理表

当前操作 表达式 计算过程 结果
加法 a + b curr + num curr + num
减法 a - b curr - num curr - num
乘法 a * b curr - prev + prev * num (curr - prev) + (prev * num)

代码实现

C# 实现

public class Solution {
    private List<string> result;
    private string num;
    private int target;
    
    public IList<string> AddOperators(string num, int target) {
        this.result = new List<string>();
        this.num = num;
        this.target = target;
        
        if (string.IsNullOrEmpty(num)) return result;
        Backtrack(0, 0, 0, "");
        return result;
    }
    
    private void Backtrack(int index, long eval, long multed, string expr) {
        if (index == num.Length) {
            if (eval == target) {
                result.Add(expr);
            }
            return;
        }
        
        long curr = 0;
        int start = index;
        
        while (index < num.Length) {
            if (index != start && num[start] == '0') break;
            curr = curr * 10 + (num[index] - '0');
            
            if (start == 0) {
                Backtrack(index + 1, curr, curr, expr + curr);
            } else {
                Backtrack(index + 1, eval + curr, curr, expr + "+" + curr);
                Backtrack(index + 1, eval - curr, -curr, expr + "-" + curr);
                Backtrack(index + 1, eval - multed + multed * curr, multed * curr, expr + "*" + curr);
            }
            
            index++;
        }
    }
}

Python 实现

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        def backtrack(index, eval, multed, expr):
            if index == len(num):
                if eval == target:
                    result.append(expr)
                return
            
            curr = 0
            start = index
            
            while index < len(num):
                if index != start and num[start] == '0':
                    break
                curr = curr * 10 + int(num[index])
                
                if start == 0:
                    backtrack(index + 1, curr, curr, str(curr))
                else:
                    backtrack(index + 1, eval + curr, curr, expr + '+' + str(curr))
                    backtrack(index + 1, eval - curr, -curr, expr + '-' + str(curr))
                    backtrack(index + 1, eval - multed + multed * curr, multed * curr, expr + '*' + str(curr))
                
                index += 1
        
        result = []
        if not num:
            return result
        backtrack(0, 0, 0, "")
        return result

C++ 实现

class Solution {
private:
    vector<string> result;
    string num;
    int target;
    
    void backtrack(int index, long eval, long multed, string expr) {
        if (index == num.length()) {
            if (eval == target) {
                result.push_back(expr);
            }
            return;
        }
        
        long curr = 0;
        int start = index;
        
        while (index < num.length()) {
            if (index != start && num[start] == '0') break;
            curr = curr * 10 + (num[index] - '0');
            
            if (start == 0) {
                backtrack(index + 1, curr, curr, expr + to_string(curr));
            } else {
                backtrack(index + 1, eval + curr, curr, expr + "+" + to_string(curr));
                backtrack(index + 1, eval - curr, -curr, expr + "-" + to_string(curr));
                backtrack(index + 1, eval - multed + multed * curr, multed * curr, expr + "*" + to_string(curr));
            }
            
            index++;
        }
    }
    
public:
    vector<string> addOperators(string num, int target) {
        this->num = num;
        this->target = target;
        
        if (num.empty()) return result;
        backtrack(0, 0, 0, "");
        return result;
    }
};

执行结果

C# 实现

  • 执行用时：628 ms
  • 内存消耗：42.5 MB

Python 实现

  • 执行用时：892 ms
  • 内存消耗：15.2 MB

C++ 实现

  • 执行用时：156 ms
  • 内存消耗：16.8 MB

性能对比

语言 执行用时 内存消耗 特点
C# 628 ms 42.5 MB 代码结构清晰，性能中等
Python 892 ms 15.2 MB 代码最简洁，但性能较差
C++ 156 ms 16.8 MB 性能最优，内存占用适中

代码亮点

  1. 🎯 使用回溯算法高效处理所有可能的组合
  2. 💡 巧妙处理乘法优先级问题
  3. 🔍 有效处理前导零和数字长度限制
  4. 🎨 代码结构清晰，易于理解和维护

常见错误分析

  1. 🚫 未正确处理前导零
  2. 🚫 忽略乘法优先级
  3. 🚫 整数溢出问题
  4. 🚫 字符串拼接效率问题

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
回溯法 O(4^n) O(n) 可以找到所有解 时间复杂度高
动态规划 O(n^3) O(n^2) 可以优化某些情况 不适用于本题
暴力枚举 O(3^n) O(n) 实现简单 效率低下

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第282题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！