Hard

题目描述

给定一个只包含数字的字符串 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 <= 10
  • num 只包含数字
  • -2^31 <= target <= 2^31 - 1

解题思路

这是一个典型的回溯算法问题。我们需要尝试所有可能的数字分割方式和运算符组合。

核心思路：

  1. 数字分割：对于字符串中的每个位置，我们可以选择在此处分割数字，或者继续延伸当前数字。需要注意避免前导零（除了单独的"0"）。

  2. 运算符处理：在每两个数字之间插入 +、- 或 * 运算符。关键在于正确处理运算符优先级。

  3. 优先级处理：由于乘法优先级高于加减法，我们不能简单地从左到右计算。解决方案是：

    • 维护当前表达式的值 currentValue
    • 维护上一个操作数的值 lastOperand
    • 遇到乘法时，先撤销上一个操作数的影响，再加上新的乘积结果

  4. 回溯过程：

    • 尝试所有可能的数字长度（从当前位置开始）
    • 对于第一个数字，直接设置为当前值
    • 对于后续数字，尝试三种运算符，递归处理剩余部分

关键技巧：

  • 使用 long long 避免整数溢出
  • 正确处理乘法运算符的优先级
  • 剪枝：避免生成无效的前导零数字

代码实现

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> result;
        backtrack(num, target, 0, "", 0, 0, result);
        return result;
    }
    
private:
    void backtrack(const string& num, int target, int index, string expression, 
                   long long currentValue, long long lastOperand, vector<string>& result) {
        if (index == num.length()) {
            if (currentValue == target) {
                result.push_back(expression);
            }
            return;
        }
        
        for (int i = index; i < num.length(); i++) {
            string currentNum = num.substr(index, i - index + 1);
            
            // 避免前导零
            if (currentNum.length() > 1 && currentNum[0] == '0') {
                break;
            }
            
            long long currentVal = stoll(currentNum);
            
            if (index == 0) {
                // 第一个数字
                backtrack(num, target, i + 1, currentNum, currentVal, currentVal, result);
            } else {
                // 加法
                backtrack(num, target, i + 1, expression + "+" + currentNum, 
                         currentValue + currentVal, currentVal, result);
                
                // 减法
                backtrack(num, target, i + 1, expression + "-" + currentNum, 
                         currentValue - currentVal, -currentVal, result);
                
                // 乘法
                backtrack(num, target, i + 1, expression + "*" + currentNum, 
                         currentValue - lastOperand + lastOperand * currentVal, 
                         lastOperand * currentVal, result);
            }
        }
    }
};

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        result = []
        
        def backtrack(index, expression, current_value, last_operand):
            if index == len(num):
                if current_value == target:
                    result.append(expression)
                return
            
            for i in range(index, len(num)):
                current_num = num[index:i+1]
                
                # 避免前导零
                if len(current_num) > 1 and current_num[0] == '0':
                    break
                
                current_val = int(current_num)
                
                if index == 0:
                    # 第一个数字
                    backtrack(i + 1, current_num, current_val, current_val)
                else:
                    # 加法
                    backtrack(i + 1, expression + "+" + current_num, 
                             current_value + current_val, current_val)
                    
                    # 减法
                    backtrack(i + 1, expression + "-" + current_num, 
                             current_value - current_val, -current_val)
                    
                    # 乘法
                    backtrack(i + 1, expression + "*" + current_num, 
                             current_value - last_operand + last_operand * current_val, 
                             last_operand * current_val)
        
        backtrack(0, "", 0, 0)
        return result

public class Solution {
    public IList<string> AddOperators(string num, int target) {
        var result = new List<string>();
        Backtrack(num, target, 0, "", 0, 0, result);
        return result;
    }
    
    private void Backtrack(string num, int target, int index, string expression, 
                          long currentValue, long lastOperand, IList<string> result) {
        if (index == num.Length) {
            if (currentValue == target) {
                result.Add(expression);
            }
            return;
        }
        
        for (int i = index; i < num.Length; i++) {
            string currentNum = num.Substring(index, i - index + 1);
            
            // 避免前导零
            if (currentNum.Length > 1 && currentNum[0] == '0') {
                break;
            }
            
            long currentVal = long.Parse(currentNum);
            
            if (index == 0) {
                // 第一个数字
                Backtrack(num, target, i + 1, currentNum, currentVal, currentVal, result);
            } else {
                // 加法
                Backtrack(num, target, i + 1, expression + "+" + currentNum, 
                         currentValue + currentVal, currentVal, result);
                
                // 减法
                Backtrack(num, target, i + 1, expression + "-" + currentNum, 
                         currentValue - currentVal, -currentVal, result);
                
                // 乘法
                Backtrack(num, target, i + 1, expression + "*" + currentNum, 
                         currentValue - lastOperand + lastOperand * currentVal, 
                         lastOperand * currentVal, result);
            }
        }
    }
}

var addOperators = function(num, target) {
    const result = [];
    
    function backtrack(index, path, value, prev) {
        if (index === num.length) {
            if (value === target) {
                result.push(path);
            }
            return;
        }
        
        for (let i = index; i < num.length; i++) {
            const str = num.slice(index, i + 1);
            const curr = parseInt(str);
            
            // Skip numbers with leading zeros (except single digit 0)
            if (str.length > 1 && str[0] === '0') break;
            
            if (index === 0) {
                backtrack(i + 1, str, curr, curr);
            } else {
                // Addition
                backtrack(i + 1, path + '+' + str, value + curr, curr);
                
                // Subtraction
                backtrack(i + 1, path + '-' + str, value - curr, -curr);
                
                // Multiplication
                backtrack(i + 1, path + '*' + str, value - prev + prev * curr, prev * curr);
            }
        }
    }
    
    backtrack(0, '', 0, 0);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N × 4^N)N为字符串长度，每个位置可以选择分割或不分割，每两个数字间可以选择3种运算符
空间复杂度O(N)递归调用栈的深度最多为N，表达式字符串长度也是O(N)

相关题目