Some thougths


  • 1

    The following DFS is similar to top solutions.

        vector<string> addOperators(string num, int target) {
            vector<string> exp;
            string cur;
            dfs(0,0,0,target,cur,num,exp);
            return exp;
        }
        void dfs(int p, int prod, long res, int target, string& cur, string &num,vector<string>& exp) {
            int n = num.size();
            if(p==n && res==target) exp.push_back(cur);
            long v = 0;
            int sz = cur.size(); 
            string s;
            for(int i=p;i<n;i++) {
                v=v*10+num[i]-'0';
                s+=num[i];
                if(cur.empty()) dfs(i+1,v,res+v,target,cur+=s,num,exp);
                else {
                    dfs(i+1,v,res+v,target,cur+='+'+s,num,exp);
                    cur.resize(sz);
                    dfs(i+1,-v,res-v,target,cur+='-'+s,num,exp);
                    cur.resize(sz);
                    dfs(i+1,prod*v,res-prod+prod*v,target,cur+='*'+s,num,exp);
                }
                cur.resize(sz);
                if(!v) return;
            }
        }
    

    Time complexity O(4^n)
    T(n) = 3 * T(n-1) + 3 * T(n-2) + 3 * T(n-3) + ... + 3 *T(1);
    T(n-1) = 3 * T(n-2) + 3 * T(n-3) + ... 3 * T(1);
    Thus T(n) = 4T(n-1);

    Space complexity O(n)
    Ignoring the large output, space complexity is depth of the recursion.

    Most recursions can be speeded up by memorization. How about this one? No, because there is no duplicate states.

    How about BFS? If a problem can be solved by one, we can solve it by the other. DFS has much lower memory requirements than BFS because it is not necessary to store all the children at each level. The search space is exponential so BFS space complexity is exponential which makes it not acceptable.


  • 0
    Y
    This post is deleted!

Log in to reply
 

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