c++ solution 3ms using hashmap and divide&conquer


  • 0
    S

    class Solution {
    public:
    unordered_map<string,vector<int>> rec;

    int compute(int a,int b,char op){
        switch(op){
            case '+': return a+b;
            case '-': return a-b;
            case '*': return a*b;
            default: return 0;
        }
    }
    string generatekey(int num1,int num2){
        return to_string(num1)+"-"+to_string(num2);
    }
    vector<int> solve(vector<int>& num,
                      vector<char>& op,
                      int start, 
                      int end){
        string index=generatekey(start,end);
        if(rec.find(index)!=rec.end())return rec[index];
        if(start==end)return vector<int>(1,num[start]);
        vector<int> left,right,diff;
        for(int i=start;i<end;i++){
            left=solve(num,op,start,i);
            right=solve(num,op,i+1,end);
            for(int j=0;j<left.size();j++){
                for(int k=0;k<right.size();k++){
                    diff.push_back(compute(left[j],right[k],op[i]));
                }
            }
        }
        rec[index]=diff;
        return diff;
    }
    vector<int> diffWaysToCompute(string input) {
        vector<int> num;
        vector<char> op;
        int number=0;
        for(char x:input){
            int k=x-'0';
            if(k>=0&&k<10){
                number=number*10+k;
            }
            else{ 
                op.push_back(x);
                num.push_back(number);
                number=0;
            }
        }
        num.push_back(number);
        return solve(num,op,0,num.size()-1);
    }
    

    };


Log in to reply
 

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