282. Expression Add Operators - cocoder39/coco39_LC GitHub Wiki

282. Expression Add Operators

    1. differentiate first number vs op+subsequent_num
    1. to handle mul, we need to note the last operand we processed
    • 2 + 3 * 4:
      • before * 4, exp_res = 2+3=5, last_operand = 3
      • when applying * 4, exp_res = exp_res - last_operand + last_operand * 4 = 5 - 3 + 3*4 = 14, last_operand = last_operand * 4 = 3 * 4 = 12
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        res = []
        self.helper(num, target, res, 0, '', 0, 0)
        return res
    

    def helper(self, num: str, target: int, res: list, start: int, expression: str, exp_res: int, last_operand: int):
        if start == len(num):
            if exp_res == target:
                res.append(expression)
            return

        for i in range(start, len(num)):
            # avoid leading 0
            if num[start] == '0' and i > start:
                return
            
            num_str = num[start:i+1] # ensure at least one letter
            cur_num = int(num_str)
            if start == 0:
                # initial number
                self.helper(num, target, res, i+1, num_str, cur_num, cur_num)
            else: # add operations
                self.helper(num, target, res, i+1, expression+'+'+num_str, exp_res+cur_num, cur_num)
                self.helper(num, target, res, i+1, expression+'-'+num_str, exp_res-cur_num, -cur_num)
                # removing the effect of the previous operand and adding the new product
                self.helper(num, target, res, i+1, expression+'*'+num_str, exp_res-last_operand+last_operand*cur_num, last_operand*cur_num)

corner case:

  • leading '0'
  • overflow => long
  • when start == 0, only generate a value, since each operation is binary
t(n) = 3t(n-1) + 3t(n-2) = ...
t(n+1) = 3t(n) + 3t(n-1) + ... = 4t(n)
time complexity is O(4 ^ n)

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        helper(res, "", num, 0, target, 0, 0);
        return res;
    }
private:    
    void helper(vector<string>& res, string expr, string& num, int start, int target, long accu, long mult) {
        if (start == num.length()) {
            if (target == accu) {
                res.push_back(expr);
            }
            return;
        }
        
        for (int i = start; i < num.length(); i++) {
            if (i != start && num[start] == '0')    return;
            string nstr = num.substr(start, i - start + 1);
            long nval = stol(nstr);
            if (start == 0) { //add an val only, cannot add op 
                helper(res, nstr, num, i + 1, target, nval, nval);
            } else { //add an op for the val
                helper(res, expr + "+" + nstr, num, i + 1, target, accu + nval, nval);
                helper(res, expr + "-" + nstr, num, i + 1, target, accu - nval, -nval);
                helper(res, expr + "*" + nstr, num, i + 1, target, accu - mult + mult * nval, mult * nval);
            }
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️