cpp 4ms, naive divide and conquer method


  • 0
    C
    class Solution {
            public:
                vector<int> dc(vector<int> &nums, vector<char> &opt, int begin, int end) {
                    if (begin + 1 == end) return vector<int>{nums[begin]};
                    vector<int> result;
                    for (int nextEnd = begin + 1; nextEnd < end; nextEnd++) {
                        vector<int> left = dc(nums, opt, begin, nextEnd);
                        vector<int> right = dc(nums, opt, nextEnd, end);
                        for (int l: left) {
                            for (int r: right) {
                                result.push_back(opt[nextEnd - 1] == '+'? l + r: opt[nextEnd - 1] == '-'? l - r: l*r);
                            }
                        }
                    }
                    return result;
                }
                vector<int> diffWaysToCompute(string input) {
                    vector<int> nums;
                    vector<char> opt;
                    int start = 0;
                    while (start < input.size()) {
                        if (!isdigit(input[start])) {
                            opt.push_back(input[start++]);
                            continue;
                        }
                        int nextStart = start + 1;
                        while (nextStart < input.size() && isdigit(input[nextStart])) nextStart++;
                        nums.push_back(stoi(input.substr(start, nextStart - start)));
                        start = nextStart;
                    }
                    return dc(nums, opt, 0, nums.size());
                }
            };

Log in to reply
 

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