Sharing my 4ms C++ solution


  • 0
    T
    class Solution {
    private:
        vector<int> diffWaysToComputeHelper(vector<int>& numbers, vector<char>& operators, int left, int right)
        {
            vector<int> result;
            if(left==right)
            {
                result.push_back(numbers[left]);
                return result;
            }
            else
            {
                int i, j, k;
                for(i=left; i<right; i++)
                {
                    vector<int> lresult = diffWaysToComputeHelper(numbers, operators, left, i);
                    vector<int> rresult = diffWaysToComputeHelper(numbers, operators, i+1, right);
                    for(j=0; j<lresult.size(); j++)
                        for(k=0; k<rresult.size(); k++)
                        {
                            if(operators[i] == '*')
                                result.push_back(lresult[j]*rresult[k]);
                            else if(operators[i] == '+')
                                result.push_back(lresult[j]+rresult[k]);
                            else
                                result.push_back(lresult[j]-rresult[k]);
                        }
                }
                return result;
            }
        }
        
    public:
        vector<int> diffWaysToCompute(string input) {
            int n = input.length();
            vector<int> numbers;
            vector<char> operators;
            int start=0, i;
            for(i=0; i<n; i++)
            {
                if(input[i] == '*' || input[i] == '+' || input[i] == '-')
                {
                    operators.push_back(input[i]);
                    numbers.push_back(atoi(input.substr(start, i-start).c_str()));
                    start = i + 1;
                }
            }
            numbers.push_back(atoi(input.substr(start, n-start).c_str()));
            
            vector<int> result;
            n = operators.size();
            result = diffWaysToComputeHelper(numbers, operators, 0, n);
            return result;
        }
    };

Log in to reply
 

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