17 lines solution, dfs (C++)


  • 57
    C
    class Solution {
    private:
        // cur: {string} expression generated so far.
        // pos: {int}    current visiting position of num.
        // cv:  {long}   cumulative value so far.
        // pv:  {long}   previous operand value.
        // op:  {char}   previous operator used.
        void dfs(std::vector<string>& res, const string& num, const int target, string cur, int pos, const long cv, const long pv, const char op) {
            if (pos == num.size() && cv == target) {
                res.push_back(cur);
            } else {
                for (int i=pos+1; i<=num.size(); i++) {
                    string t = num.substr(pos, i-pos);
                    long now = stol(t);
                    if (to_string(now).size() != t.size()) continue;
                    dfs(res, num, target, cur+'+'+t, i, cv+now, now, '+');
                    dfs(res, num, target, cur+'-'+t, i, cv-now, now, '-');
                    dfs(res, num, target, cur+'*'+t, i, (op == '-') ? cv+pv - pv*now : ((op == '+') ? cv-pv + pv*now : pv*now), pv*now, op);
                }
            }
        }
    
    public:
        vector<string> addOperators(string num, int target) {
            vector<string> res;
            if (num.empty()) return res;
            for (int i=1; i<=num.size(); i++) {
                string s = num.substr(0, i);
                long cur = stol(s);
                if (to_string(cur).size() != s.size()) continue;
                dfs(res, num, target, s, i, cur, cur, '#');         // no operator defined.
            }
    
            return res;
        }
    };

  • 0

    Hi, cmyzx. Thanks for your sharing. Personally, this is the most clear solution I have found in the Discuss. The part handling * in the function dfs is really fascinating :-)

    BTW, this line

    if (to_string(now).size() != t.size()) continue;
    

    can just be shortened a little bit to:

    if (to_string(now) != t) continue;

  • 6
    H
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<String>();
        //search each possible left start number
        for(int i = 1; i <= num.length(); i++){
            String left = num.substring(0, i);
            long left_long = Long.valueOf(left);
            if(!(left_long + "").equals(left)) break;//if it starts with multiyple 0s, skip them all
            DFS(num, i, target, left, left_long, left_long, '#', result);
        }
        
        return result;
    }
    
    
    public void DFS(String num, int index, int target, String leftExpr, long leftValue, long prevValue, char sign, List<String> result){
        //if we reach end of string and left value equals target
        if(index == num.length() && target == leftValue){
            result.add(leftExpr);
            return;
        }
        //start from index + 1, end at num.length, the input index is already the first index after left
        for(int i = index+1; i <= num.length(); i++){
            String right = num.substring(index, i);
            long right_long = Long.valueOf(right);
            if(!(right_long + "").equals(right)) return;//if it starts with multiple 0s, skip them all
            
            //operator between left and right is "+"
            DFS(num, i, target, leftExpr + "+" + right, leftValue + right_long, right_long, '+', result);
            
            //operator between left and right is "-"
            DFS(num, i, target, leftExpr + "-" + right, leftValue - right_long, right_long, '-', result);
            
            //operator between left and right is "*", then we merge this * with right to left
            long newLeft = 0;
            if(sign == '+'){
                //remove last number, add last number * current right
                newLeft = leftValue - prevValue + prevValue * right_long;
            }else if (sign == '-'){
                newLeft = leftValue + prevValue - prevValue * right_long;
            }else{//inital case, first left, where we don't have +/- before it 
                newLeft = prevValue * right_long;
            }
            //since we merge a * b to a new a, we will keep the sign before a
            DFS(num, i, target, leftExpr + "*" + right, newLeft, prevValue*right_long, sign, result);
        }
    }
    

    Cool Solution! I write your solution in Java and add comments.
    Basically, you recursively expand left operand and keep last number added into the left. So if the next
    operator is "*", you can update the last number in left accordingly


  • -4
    C

    Hi, cmyzx,

    This solution cannot pass test case of sol.addOperators("2147483648", -2147483648);


  • 0
    P

    the size check probably is better I think. It avoids one more string equality call.


  • 0

    Are you serious? Have you tested it on the OJ? The code just gets accepted... I guess you may have used int in the places where long should be used...


  • 0

    Great comments!


  • 0
    C

    It looks like that leetcode doesn't check this test case. Even though the above code pass OJ, I run the codes on my machine, the return result is empty which is wrong. In the first iteration, it always push the number into string directly, there's no way to generate string starting with '-'.


  • 0

    Well, the OJ has included this test case. In fact, you've misunderstood the problem, which says

    add operators +, -, or * between the digits

    So it makes no sense to just add a negative sign at the beginning.


  • 0
    R

    Can someone please help me understand why the past value during multiplication operation is not "now" instead its "pv*now" unlike other cases ? Thank you. - Reshmy


  • 1
    T

    Think about operator precedence. * has more precedence than +/-. If last one is +/- and current op is *, you have to do * first and then +/-.


  • 0
    C

    Can you explain me the multiplicative part of the solution. Thanks in advance.


  • 0
    Z

    if (to_string(cur).size() != s.size()) continue; Could you explain this part? Thx


  • 1
    A

    Great answer! here's python version

    def addOperators(self, num, target):
        self.ans = []
        self.target = target
        for i in xrange(1, len(num)+1):
            if i > 1 and num[0] == '0':
                continue
            self.dfs(num[i:], int(num[:i]), num[:i], int(num[:i]), '#')
        
        return self.ans
    
    def dfs(self, num, current, tmpAns, pre_val, pre_op):
        if not num:
            if self.target == current:
                self.ans.append(tmpAns)
            return
        
        for i in xrange(1, len(num)+1):
            if i > 1 and num[0] == '0':
                continue
            now = int(num[:i])
            self.dfs(num[i:], current+now, tmpAns + '+' + num[:i], now, '+')
            self.dfs(num[i:], current-now, tmpAns + '-' + num[:i], now, '-')
            
            if pre_op == '+':
                self.dfs(num[i:], current-pre_val + pre_val*now, tmpAns + '*' + num[:i], pre_val*now, pre_op)
            elif pre_op == '-':
                self.dfs(num[i:], current+pre_val - pre_val*now, tmpAns + '*' + num[:i], pre_val*now, pre_op)
            else:
                self.dfs(num[i:], current * now, tmpAns + '*' + num[:i], pre_val*now, pre_op)
    

  • 0
    I

    If I replace op to '*' for multiplication instead of passing what was passed, I got wrong answer. Can anyone tell me why it is so?


  • 0
    U

    The value for multiplication of (pv*now) has already been calculated and you can regard this result as a new value that is associated with the previous operator ('+' or '-' or '#').


  • 4
    H

    Nice solution! I rewrite in C++ with less code.

    class Solution {
    public:
        vector<string> addOperators(string num, int target) {
            vector<string> res;
            dfs(num, target, 0, 0, 0, "", res);
            return res;
        }
        
        void dfs(string& s, int target, int pos, long cv, long pv, string r, vector<string>& res) {
            if (pos == s.size() && cv == target) {
                res.push_back(r);
                return;
            }
            for (int i = 1; i <= s.size() - pos; i++) {
                string t = s.substr(pos, i);
                if (i > 1 && t[0] == '0') continue; // preceding 
                long n = stol(t);
                if (pos == 0) {
                    dfs(s, target, i, n, n, t, res);
                    continue;
                }
                dfs(s, target, pos+i, cv+n, n, r+"+"+t, res);
                dfs(s, target, pos+i, cv-n, -n, r+"-"+t, res);
                dfs(s, target, pos+i, cv-pv+pv*n, pv*n, r+"*"+t, res);
            }
        }
    };
    

  • 0
    B

    Nice solution, can you please share the thought process of deriving how to handle substrings? When I first look at the problem, the first thing came to my mind is to get all combinations of digits first, then for each combination do the DFS.

    How did you manage to make sure you cover all substrings and dfs in the same logic?


  • 1
    H

    if (to_string(cur).size() != s.size()) continue;
    if (to_string(now).size() != t.size()) continue;

    No need to continue here, just break


  • 0
    T

    @huanyan_hny Exactly, I am thinking the same way. In that case, it can save some iterations. My code accepted with the following conditions:

    if (to_string(nowVal).length() != t.size()) break;
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.