C++ 8ms recursive solution


  • 0
    X
    class Solution {
    public:
    	int calc(int a, int b, char op) {
    		if (op == '+') {
    			return a + b;
    		}
    		else if (op == '-') {
    			return a - b;
    		}
    		else if (op == '*') {
    			return a * b;
    		}
    		return 0;
    	}
    
    	vector<int> recur(int l, int r, string& input) {
    		vector<int> ans;
    		for (int i = l; i <= r; ++i) {
    			if (!isdigit(input[i])) {
    				vector<int> left = recur(l, i - 1, input);
    				vector<int> right = recur(i + 1, r, input);
    				for (auto l : left) {
    					for (auto r : right) {
    						int tmp = calc(l, r, input[i]);
    						ans.push_back(tmp);
    					}
    				}
    			}
    		}
    		if (ans.empty()) {
    			int num;
    			stringstream ss;
    			ss << input.substr(l, r - l + 1);
    			ss >> num;
    			ans = vector<int>{ num };
    		}
    		return ans;
    	}
    
    	vector<int> diffWaysToCompute(string input) {
    		return recur(0, input.size() - 1, input);
    	}
    };

Log in to reply
 

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