My concise backtracking code


  • 0
    O
    class Solution {
    private:
        unordered_map<string, vector<int>> calculated;
    public:
        vector<int> diffWaysToCompute(string input) {
            if (calculated.find(input) != calculated.end())
                return calculated[input];
            vector<int> ans;
            int n = 0;
            for (int i = 0; i < input.size(); i++) {
                if (input[i] == '+') {
                    for (int right : diffWaysToCompute(input.substr(0, i))) {
                        for (int left : diffWaysToCompute(input.substr(i + 1))) {
                            ans.push_back(right + left);
                        }
                    }
                }
                else if (input[i] == '-') {
                    for (int right : diffWaysToCompute(input.substr(0, i))) {
                        for (int left : diffWaysToCompute(input.substr(i + 1))) {
                            ans.push_back(right - left);
                        }
                    }
                }
                else if (input[i] == '*') {
                    for (int right : diffWaysToCompute(input.substr(0, i))) {
                        for (int left : diffWaysToCompute(input.substr(i + 1))) {
                            ans.push_back(right * left);
                        }
                    }
                }
                else {
                    n = n * 10 + input[i] - '0';
                }
            }
            if (ans.size() == 0)
                ans.push_back(n);
            calculated[input] = ans;
            return ans;
        }
    };
    

Log in to reply
 

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