[recommend for beginners]clean C++ implementation with detailed explanation


  • 24
    class Solution {
    public:
        vector<string> addOperators(string num, int target) {
            vector<string> result;
            if(num.size()==0)   return result;
            help(result, "", num, target, 0, 0, 0);
            return result;
        }
        
        void help(vector<string> &result, string path, string num, int target, int pos, long cur, long prev){
            if(pos==num.size()){
                if(cur==target)   result.push_back(path);
                return;
            }
            for(int i=pos; i<num.size(); i++){
                /*** corner-case-added-code ***/
                if(num[pos]=='0' && i>pos) break;
                string _str=num.substr(pos, i-pos+1);
                long _value=stol(_str);
                if(pos==0)  {
                    help(result, path+_str, num, target, i+1, _value, _value);
                }
                else{
                    help(result, path+"+"+_str, num, target, i+1, cur+_value, _value);
                    help(result, path+"-"+_str, num, target, i+1, cur-_value, -_value);
                    help(result, path+"*"+_str, num, target, i+1, cur-prev+prev*_value, prev*_value);
                }
            }
        }
    };

  • 0
    2

    This problem is a really typical DFS state memorization problem

    class Solution {
    public:
        vector<string> addOperators(string num, int target) {
            vector<string> result;
            if(num.size() == 0)  return result;
            help(result, "", num, target, 0, 0, 0);
            return result;
        }
        
        void help(vector<string>& result, string path, string num, int target, int pos, long cur, long prev) {
            if(pos == num.size()) {
                if(target == cur)  result.push_back(path);
                return;
            }
            
            for(int i = pos; i < num.size(); i++) {
                if(num[pos] == '0' && i > pos)  break;
                string sub_str = num.substr(pos, i - pos + 1);
                long sub_int = stol(sub_str);
                if(pos == 0) {
                    help(result, path + sub_str, num, target, i + 1, sub_int, sub_int);
                }
                else {
                    help(result, path + "+" + sub_str, num, target, i + 1, cur + sub_int, sub_int);
                    help(result, path + "-" + sub_str, num, target, i + 1, cur - sub_int, -sub_int);
                    help(result, path + "*" + sub_str, num, target, i + 1, cur - prev + prev * sub_int, prev * sub_int);
                }
            }
        }
    };

  • 2
    B

    Could you explain the logic for cur and pre value for product, why can t we have similar dfs call of the help function as addition and subtraction. With that Structure I am getting Output limit exceeded but i guess results are right.


  • 0
    B

    Just understood its because of the associaviity of the operators


  • 0
    F

    Impressive but difficult to implement solutions

    class Solution {
    public:
        vector<string> addOperators(string num, int target) {
            vector<string> result;
            if (num.size() == 0) return result;
            dfs(result, "", num, target, 0, 0, 0);
            return result;
        }
        
        void dfs(vector<string>& result, string path, string num, int target, int pos, long cur, long prev) {
            if (pos == num.size()) {
                if (cur == target) result.push_back(path);
                return;
            }
            for (int i = pos; i < num.size(); i++) {
                if (num[pos] == '0' && i > pos) break;
                string _str = num.substr(pos, i - pos + 1);
                long _value = stol(_str);
                if (pos == 0) {
                    dfs(result, path + _str, num, target, i + 1, _value, _value);
                }
                else {
                    dfs(result, path + "+" + _str, num, target, i + 1, cur + _value, _value);
                    dfs(result, path + "-" + _str, num, target, i + 1, cur - _value, -_value);
                    dfs(result, path + "*" + _str, num, target, i + 1, cur - prev + prev * _value, prev * _value);
                }
            }
        }
    };

  • 3

    @fight.for.dream Actually it's a very direct solution in backtracking, get more practice in backtracking and you'll find it rather simple except for some corner cases. Have fun in Leetcode.


  • 0
    F

    @LHearen Thanks for your advice !


  • 1
    T

    is the time complexity 3^N and space complexity 3^N???


  • 0

    @TarzanNJane
    Each digit has four different options: +, -, *, nothing.
    So I think time complexity is 4^N.


  • 2
    A

    @RainbowSecret where is the detailed explanation?


  • 1
    R

    Where is the detailed explanation?


  • 1
    F

    @RainbowSecret
    Where is the detailed explanation?


  • 0
    F

    @bloomer Can you please explain by what you said regarding associativity?


  • 0
    E

    Excuse me if I missed something but where is the detailed explanation?


Log in to reply
 

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