Clean AC C++ solution with explanation


  • 6
    R

    The idea is that you just search through the string, and find the operators position, then recursively solve the results of the left and right of the operator, and once having the left and right results, compute the final result with the operator.

    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            map<string, vector<int>> cache;
            return diffWaysToCompute(input, 0, input.size()-1, cache);
        }
    private:
        vector<int> diffWaysToCompute(string& input, int start, int end, map<string, vector<int>>& cache) {
            string key=to_string(start)+to_string(end);
            if(cache.count(key)) return cache[key];
            vector<int> result;
            int num=0;
    	    for(int i=start; i<=end; ++i) {
    	        if(input[i]!='+' && input[i]!='-' && input[i]!='*')
    	            num=num*10+(input[i]-'0');
    		    else{ 
        		    vector<int> left=diffWaysToCompute(input, start, i-1, cache);
        		    vector<int> right=diffWaysToCompute(input, i+1, end, cache);
        		    for(int l=0; l<left.size(); ++l){
        		        for(int r=0; r<right.size(); ++r){
        		            if(input[i]=='+'){
        		                result.push_back(left[l]+right[r]);
        		            }else if(input[i]=='-'){
        		                result.push_back(left[l]-right[r]);
        		            }else if(input[i]=='*'){
        		                result.push_back(left[l]*right[r]);
        		            }               
        		        }
        		    }
    		    }    
            }
            if(result.size()==0) result.push_back(num); //only single number
            return cache[key]=result;
        }
    };

  • 0
    X

    I think there is a bug for the line " string key=to_string(start)+to_string(end);". For example, if the start is 2, and end is 345, the key is "2345". But cannot to differentiate it with start=23 and end=45. So tiny fix can make it work: " string key=to_string(start)+ "-" + to_string(end);".


Log in to reply
 

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