Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/282.html

 282	Expression Add Operators

 Given a string that contains only digits 0-9 and a target value,
 return all possibilities to add binary operators (not unary) +, -, or * between the digits
    so they evaluate to the target value.

 Example 1:

 Input: num = "123", target = 6
 Output: ["1+2+3", "1*2*3"]

 Example 2:

 Input: num = "232", target = 8
 Output: ["2*3+2", "2+3*2"]

 Example 3:

 Input: num = "105", target = 5
 Output: ["1*0+5","10-5"]

 Example 4:

 Input: num = "00", target = 0
 Output: ["0+0", "0-0", "0*0"]

 Example 5:

 Input: num = "3456237490", target = 9191
 Output: []

Algorithm

We need two variables diff and sumUpToPrevNum, one is used to record the value to be changed, the other is the value after the current operation, and they all need to use long type, because the string is converted to int type, it is easy to overflow.

For addition and subtraction, diff is the negative value of the number to be added and the number to be subtracted.

For multiplication, it’s a bit more complicated, diff is the diff of the last change multiplied by the number to be multiplied.

For example, for example, 2+3*2, when the calculation is about to multiply by 2, the last cycle of sumUpToPrevNum = 5, diff = 3, and if we want to calculate this multiplication by 2, the new change value diff should It is 32=6, and we need to remove the result of the previous +3 operation, and add a new diff, namely (5-3)+6=8, which is the value of the new expression 2+32.

Another thing to note is that if the input is “000”, 0, the following errors are prone to occur:

Wrong: ["0+0+0","0+0-0","0+0*0","0-0+0","0-0-0","0-0*0" ,"0*0+0","0*0-0","0*0*0","0+00","0-00","0*00","00+0"," 00-0","00*0","000"]

Correct:["0*0*0","0*0+0","0*0-0","0+0*0","0+0+0","0+0-0" ,"0-0*0","0-0+0","0-0-0"]

Code

Java

  • import java.util.ArrayList;
    import java.util.List;
    
    public class Expression_Add_Operators {
    
        class Solution {
    
            public List<String> addOperators(String num, int target) {
    
                ArrayList<String> result = new ArrayList<String>();
    
                if (num.length() == 0) {
                    return result;
                }
    
                dfs(num, target, 0, 0, "", result);
    
                return result;
            }
    
            // `diff` is for rollback previous `*` operation
            void dfs(String digitString, int target, long diff, long sumUpToPrevNum, String oneResult, ArrayList<String> res) {
    
                if (digitString.length() == 0 && sumUpToPrevNum == target) {
                    res.add(oneResult);
                    return;
                }
    
                for (int i = 1; i <= digitString.length(); ++i) {
    
                    // divide and conquer
                    String cur = digitString.substring(0, i);
                    String next = digitString.substring(i);
    
                    if (cur.length() > 1 && cur.charAt(0) == '0') { // @note: skip '000', but single '0' is ok
                        return;
                    }
    
                    if (oneResult.length() > 0) {
                        dfs(next, target, Long.valueOf(cur), sumUpToPrevNum + Long.valueOf(cur), oneResult + "+" + cur, res);
                        dfs(next, target, -1 * Long.valueOf(cur), sumUpToPrevNum - Long.valueOf(cur), oneResult + "-" + cur, res);
                        dfs(next, target, diff * Long.valueOf(cur), (sumUpToPrevNum - diff) + diff * Long.valueOf(cur), oneResult + "*" + cur, res);
                    } else {
                        dfs(next, target, Long.valueOf(cur), Long.valueOf(cur), cur, res); // use `cur` as oneResult
                    }
                }
            }
        }
    }
    
  • class Solution {
    public:
        vector<string> addOperators(string num, int target) {
            vector<string> res;
            helper(num, target, 0, 0, "", res);
            return res;
        }
        void helper(string num, int target, long diff, long curNum, string out, vector<string>& res) {
            if (num.size() == 0 && curNum == target) {
                res.push_back(out); return;
            }
            for (int i = 1; i <= num.size(); ++i) {
                string cur = num.substr(0, i);
                if (cur.size() > 1 && cur[0] == '0') return;
                string next = num.substr(i);
                if (out.size() > 0) {
                    helper(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);
                    helper(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res);
                    helper(next, target, diff * stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res);
                } else {
                    helper(next, target, stoll(cur), stoll(cur), cur, res);
                }
            }
        }
    };
    
  • class Solution:
        def addOperators(self, num: str, target: int) -> List[str]:
            ans = []
    
            def dfs(start, prev, curr, path):
                if start == len(num):
                    if curr == target:
                        ans.append(path)
                    return
                for i in range(start, len(num)):
                    if i != start and num[start] == '0':
                        break
                    next = int(num[start: i + 1])
                    if start == 0:
                        dfs(i + 1, next, next, path + str(next))
                    else:
                        dfs(i + 1, next, curr + next, path + "+" + str(next))
                        dfs(i + 1, -next, curr - next, path + "-" + str(next))
                        dfs(
                            i + 1,
                            prev * next,
                            curr - prev + prev * next,
                            path + "*" + str(next),
                        )
    
            dfs(0, 0, 0, "")
            return ans
    
    ############
    
    class Solution(object):
      def addOperators(self, num, target):
        res, self.target = [], target
        for i in range(1, len(num) + 1):
          if i == 1 or (i > 1 and num[0] != "0"):  # prevent "00*" as a number
            self.dfs(num[i:], num[:i], int(num[:i]), int(num[:i]), res)  # this step put first number in the string
        return res
    
      def dfs(self, num, temp, cur, last, res):
        if not num:
          if cur == self.target:
            res.append(temp)
          return
        for i in range(1, len(num) + 1):
          val = num[:i]
          if i == 1 or (i > 1 and num[0] != "0"):  # prevent "00*" as a number
            self.dfs(num[i:], temp + "+" + val, cur + int(val), int(val), res)
            self.dfs(num[i:], temp + "-" + val, cur - int(val), -int(val), res)
            self.dfs(num[i:], temp + "*" + val, cur - last + last * int(val), last * int(val), res)
    
    

All Problems

All Solutions