[recommend for beginners]clean C++ implementation with detailed explanation


  • 6
    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            int size=input.size();
            vector<int> result;
            for(int i=0; i<size; i++){
                if(ispunct(input[i])){
                    for(int a : diffWaysToCompute(input.substr(0, i)))
                        for(int b : diffWaysToCompute(input.substr(i+1))){
                            if(input[i]=='+')  result.push_back(a+b);
                            if(input[i]=='-')  result.push_back(a-b);
                            if(input[i]=='*')  result.push_back(a*b);
                        }
                }
            }
            /*** the base case is that there are no operator-char ***/
            /*** we return vector<int>{stoi(input)} when this happens ***/
            return result.size() ? result : vector<int>{stoi(input)};
        }
    };

  • 1
    2

    The key to the solution is that we need to return

       return result.size() > 0 ? result : vector<int>{ stoi(input) };
    

    The return value is really important .....

    The recursion solution is similiar to construct all the binary tree using {1, 2... , n}

    Here is the AC implementation

    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            int size_str = input.size();
            vector<int> result;
            for(int i = 0; i < size_str; i++) {
                if(isOperator(input[i])) {
                    vector<int> left = diffWaysToCompute(input.substr(0, i));
                    vector<int> right = diffWaysToCompute(input.substr(i + 1));
                    for(int a : left) {
                        for(int b : right) {
                            if(input[i] == '+')  result.push_back(a + b);
                            if(input[i] == '-')  result.push_back(a - b);
                            if(input[i] == '*')  result.push_back(a * b);
                        }
                    }
                }
            }
            return result.size() > 0 ? result : vector<int>{ stoi(input) };
        }
            
        bool isOperator(char c) {
            return  !(c >= '0' && c <= '9');
        }
    };
    

  • 0
    2

    I forget to use stoi(string) to change from string to int value ....


  • 0
    F

    This is a typical divide and conquer solution to solve this problem....


  • 0
    F
    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            vector<int> result;
            /** check if the string contains operators **/
            if (input.size() == to_string(stoi(input)).size()) return vector<int>({stoi(input)});
            for (int i = 0; i < input.size(); i++) {
                if (isdigit(input[i])) continue;
                vector<int> lefts = diffWaysToCompute(input.substr(0, i));
                vector<int> rights = diffWaysToCompute(input.substr(i + 1));
                for (int left : lefts) {
                    for (int right : rights) {
                        switch(input[i]) {
                            case '+': result.push_back(left + right); break;
                            case '-': result.push_back(left - right); break;
                            case '*': result.push_back(left * right); break;
                        }
                    }
                }
            }
            return result;
        }
    };

  • 0

    This is so clean, a solution should be. Awesome, dude!


  • 0

    @RainbowSecret But there can be some performance problem, isn't it?

    • repeatedly substr which can be replaced by index range
    • each time the left a moves forward, the right substring will have to do another computation

  • 0

    @RainbowSecret Here is a solution paying attention to efficiency and of course result in best submission as follows:

    class Solution {
    private:
        int sLen;
        vector<int> helper(const string& s, int begin, int end)
        {
            vector<int> v;
            if(begin > end) return v; 
            for(int i = begin; i <= end; ++i)
            {
                if(!isdigit(s[i]))
                {
                    vector<int> l = helper(s, begin, i-1), r = helper(s, i+1, end);
                    for(int j = 0; j < l.size(); ++j)
                    {
                        for(int k = 0; k < r.size(); ++k)
                        {
                            switch(s[i])
                            {
                                case '-': v.push_back(l[j]-r[k]); break;
                                case '+': v.push_back(l[j]+r[k]); break;
                                case '*': v.push_back(l[j]*r[k]); break;
                            }
                        }
                    }
                }
            }
            return v.size()? v : vector<int>{stoi(s.substr(begin, end-begin+1))};
        }
    public:
        vector<int> diffWaysToCompute(string input) {
            sLen = input.length();
            return helper(input, 0, sLen-1);
        }
    };
    

Log in to reply
 

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