282. Expression Add Operators

problem description

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 thought

对于每个能放置操作符的地方，有4种情况。第一种是不放置，然后三种是放置3个不同的操作符。

将情况大概讲出来之后，就知道这里使用回溯法解决问题了。这里问题关键在于如果前面是一个加法，然后碰到一个乘法，如何解决。

这里在回溯的时候，保存前面一个操作的数字值。如果当前是乘法，就将当前值减去或者加上前面的值（相当于回溯到前面），然后将前面的值和当前数字相乘，再让前面值加上或者减去当前值。这是大概的思路。实际实现时候，可以优化。

需要注意的是，如果碰到开头为0的字符串需要处理。这里对要求对c++数字和字符串转化操作熟悉

code

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        string now="";
        help(res,target,num,0,0,now,0);
        return res;
    }
    void help(vector<string>&res,int target,string&num,long pre_value,long value,string&now,int pos){
        if(pos==num.size()&&value==target){
            res.push_back(now);
            return;
        }
        for(int i=pos;i<num.size();++i){
            string t=num.substr(pos,i-pos+1);
            if(t.size()>1&&t[0]=='0')
                continue;
            long va=stol(t);

            if(pos==0){
                help(res,target,num,va,va,t,i+1);
                continue;
            }

            int sz=now.size();
            now.push_back('+');now+=t;
            help(res,target,num,va,value+va,now,i+1);
            now[now.size()-t.size()-1]='-';
            help(res,target,num,-va,value-va,now,i+1);
            now[now.size()-t.size()-1]='*';
            help(res,target,num,pre_value*va,value-pre_value+pre_value*va,now,i+1);
            now.resize(sz);
        }
    }
};

algorithm analysis

回溯法时间复杂度分析比较困难，只需要知道这里是指数级时间复杂度。这里还有一个关键的优化在于对string的处理。我看别的答案直接使用operator +，并且没有使用左值引用减少析构和构造。时间复杂度400ms左右。在利用引用优化和+=优化之后，时间复杂度减低到了70ms左右。这么看来string的析构和构造还真挺耗时间的。