80ms C++ solution


  • 0
    W

    keep recording preSign, preNum and val to determine their values for next call

    keep appending digit to current number (unless first digit is already '0' coz there is no number format of "012")
    and call next dfs until reaching the end

    Suggestion is appreciated to make it faster...

       //time O(4^nsz) (basically insert "", "+", "-", "*" between chars in num to get final computed result, space O(nsz)
        class Solution {
        public:
        	void dfs(int idx, char preSign, long preNum, long val, const long t, string &tmp, const string &num, vector<string> &ret)
        	{
        		const int nsz=num.size();
        		if(idx>=nsz)
        		{
        			if(t==val+preNum)
        				ret.push_back(tmp);
        			return;
        		}
        		long end=num[idx]=='0'?idx:(nsz-1), n1=0, newPreNum=0, newVal=0, oldSz=tmp.size();
        		for(int i=idx; i<=end; ++i)
        		{
        			n1=10*n1+num[i]-'0';
        			tmp+=num[i];
        			if(preSign=='*')
        			{
        				newPreNum=preNum*n1;
        				newVal=val;
        			}else
        			{
        				newPreNum=preSign=='+'?n1:-n1;
        				newVal=val+preNum;
        			}
        			if(i==nsz-1)
        				dfs(i+1, ' ', newPreNum, newVal, t, tmp, num, ret);
        			else
        			{
        				tmp+='*';
        				dfs(i+1, '*', newPreNum, newVal, t, tmp, num, ret);
        				
        				tmp.back()='+';
        				dfs(i+1, '+', newPreNum, newVal, t, tmp, num, ret);
        				
        				tmp.back()='-';
        				dfs(i+1, '-', newPreNum, newVal, t, tmp, num, ret);
        				tmp.pop_back();
        			}
        		}		
        		tmp.resize(oldSz);
        	}
        
            vector<string> addOperators(string num, int target) {
                vector<string> ret;
        		string tmp;
        		dfs(0, '+', 0, 0, target, tmp, num, ret);
        		return ret;
            }
        };

Log in to reply
 

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