Typical backtracking solution with detailed explanation in C++


  • 2

    Solution

    Analysis

    Typical backtracking problem as it is. Try to split the string into small blocks and then meantime try different operators among them.

    • from a starting position, we can try different valid length for the current number but if the length is bigger than 1 and the first digit is zero then just stop;
    • using different operators to connect the current number, calculate and then store them in a temporary string for the next number till the end;
    • but when we try *, we have to be more careful since multiplier will associate its previous number and has higher precedence, so we as a result have to record its previous number; but this will require us to handle it delicately when we are inserting + or -, as for + we can just put the number as previous but as to -, we will need to set -number as previous; because we have to subtract the previous number first when inserting * - inserting means we are do the calculation with the current number here;
    • since the target is an int, so when the number is larger than INT_MAX, we should just stop there.

    Improvements

    • there will be numbers collected larger than INT_MAX, so we have to adopt long - long long here is unnecessary;
    • collecting the number one character at a time is more efficient to convert the substring directly to integer using stol;
    • using temporary substring to replace to_string(number) will save lots of converting time;
    • actually we can just use one temporary string and append the digit instead of retrieving the substring each time.

    The whole solution in C++ is as follows.

    class Solution {
    private:
        int sLen;
        void traverse(const string s, int pos, long current, long pre, int sum, string path, vector<string>& v)
        {
            if(sLen == pos) { if(current == sum) v.push_back(path); return ; }
            long num = 0;
            string t;
            for(int i = pos; i < sLen; ++i)
            {
                if(i-pos>0 && s[pos]=='0') return ;
                t += s[i];
                num = 10*num + s[i]-'0';
                if(num > INT_MAX) return ;
                if(pos == 0) traverse(s, i+1, num, num, sum, t, v);
                else
                {
                    traverse(s, i+1, current+num, num, sum, path+"+"+t, v);
                    traverse(s, i+1, current-num, -num, sum, path+"-"+t, v);
                    traverse(s, i+1, current-pre+pre*num, pre*num, sum, path+"*"+t, v);
                }
            }
        }
    public:
        vector<string> addOperators(string s, int target) {
            sLen = s.length();
            vector<string> v;
            traverse(s, 0, 0, 0, target, "", v);
            return v;
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 0
    Q

    @LHearen
    I have a question regarding to this statement:
    "since the target is an int, so when the number is larger than INT_MAX, we should just top there."
    I think we cannot give up here, because if we choose '-' as the next symbol, we still have change to come back from "long domain" to "int domain". Isn't this true?


  • 0

    @quesder Sorry about the wrong typing stop there, though I didn't quite get your point, but we have to stop there since the target is an int which implies that the numbers in the calculation process should also follow the rule int type.


Log in to reply
 

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