Leetcode 241: Different Ways to Add Parentheses

https://leetcode.com/problems/different-ways-to-add-parentheses/description/

Notes:

This question could be a very good interview question. Of course, if you cannot come up with the divide-and-conquer idea, it could be overwhelming.

We can apply () any place we want, it means we can divide it any place. So it is a question designed for the very fundamental and very powerful divide-and-conquer concept.

After dividing, we has successfully convert the original problem to a same problem but with a smaller size, so it can be solved by recursion.

For each divided part, we will calculate all the possible results from the expression, just like the original question.

So the basic case it when we have 0 element, we simply return an empty vector, {};

When we have only 1 element, we simply return a vector with that element, {v[i]};

When we have more 1 element, we need to introduce the operators between the numbers.

After we obtain all the possible results for each divided part, we can again connect them back using the operator between them. The is like the merging back concept after dividing them.

See the code below:

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        int len = input.size();
        vector<int> nums;
        for(int i=0; i<len; ){//convert the input to array
            if(input[i] >='0' && input[i] <='9'){
                int num = 0;
                while(i<len && input[i] >='0' && input[i] <='9') {
                    num = num*10 + (input[i++] - '0');
                }
                nums.push_back(num);
            }
            if(i<len && input[i] == '+' || input[i] == '-' || input[i] == '*'){
                if(input[i] == '+') nums.push_back(-1);
                else if(input[i] == '-') nums.push_back(-2);
                else nums.push_back(-3);
                ++i;
            }
        }
        return dac(nums, 0, nums.size());
    }

private:
    vector<int> dac(vector<int> &ns, int left, int right) {
        if(left >= right) return {};
        if(left + 1 == right) return {ns[left]};
        vector<int> res;
        for(int i=left; i<right; ++i){
            if(ns[i] == -1 || ns[i] == -2 || ns[i] == -3){
                vector<int> v1 = dac(ns, left, i);//divide and conquer
                vector<int> v2 = dac(ns, i+1, right);
                for(int &a : v1) {//all possible results
                    for(int &b : v2) {
                        if(ns[i] == -1) res.push_back(a+b);
                        else if(ns[i] == -2) res.push_back(a-b);
                        else res.push_back(a*b);
                    }
                }
            }
        }
        return res;
    }
};

Follow up:

It is said it is one phone interview from Google: given a array with integers, add operators, +, -, *, /, or () any places legally. Return all the possible results after the operations.

So the core algorithm used is in the above dac() function. For, /, we need to deal with 0. or data type. And we can discuss with the interviewer for these considerations.