Concise recursive solution in C++


  • 2
    K
    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            vector<int> res;
            for (int i = 0; i<input.size(); ++i) {
                if (input[i]<'0' || input[i]>'9') {  // '+' or '-' or '*'
                    vector<int> left = diffWaysToCompute(input.substr(0, i)); // left sub string
                    vector<int> right = diffWaysToCompute(input.substr(i+1)); // right sub string
                    for (auto l : left)
                        for (auto r : right) {
                            if (input[i] == '+') res.push_back(l + r);
                            else if (input[i] == '-') res.push_back(l - r);
                            else res.push_back(l * r);
                        }
                }
            }
            if (res.empty()) res.push_back(atoi(input.c_str()));   // only contain number
            return res;
        }
    };

Log in to reply
 

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