An easy-to-understand recursive solution in C++ (3 ms)


  • 0
    Q
    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            // initialize numbers and signs
            vector<int> nums;
            vector<char> signs;
            string num = "";
            for (auto c : input) {
                if (c >= '0' && c <= '9') {
                    num += c;
                } else {
                    signs.push_back(c);
                    nums.push_back(stoi(num));
                    num = "";
                }
            }
            nums.push_back(stoi(num));
            // find different computes
            return computes(nums, signs, 0, signs.size() - 1);
        }
        
        vector<int> computes(vector<int>& nums, vector<char>& signs, int start, int end) {
            if (start == end) {
                return vector<int>{calculate(nums[start], nums[start + 1], signs[start])};
            } else if (start > end) {
                return vector<int>{nums[start]};
            }
            vector<int> res;
            for (int i = start; i <= end; i++) {
                auto left = computes(nums, signs, start, i - 1);
                auto right = computes(nums, signs, i + 1, end);
                for (auto l : left) {
                    for (auto r : right) {
                        res.push_back(calculate(l, r, signs[i]));
                    }
                }
            }
            return res;
        }
        
        int calculate(int num1, int num2, char sign) {
            if (sign == '+') {
                return num1 + num2;
            } else if (sign == '-') {
                return num1 - num2;
            } else if (sign == '*') {
                return num1 * num2;
            }
        }
        
    };
    

Log in to reply
 

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