[leetcode]241. Different Ways to Add Parentheses

Analysis

ummmm—— [每天刷题并不难。。。其实已经很多天没刷了]

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

遍历input，遇到运算符就把input分成两部分，然后再分别遍历两个部分。其实这题就是让我们忽略运算符的优先级，计算出式子的所有可能结果。

Implement

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        int len = input.size();
        for(int i=0; i<len; i++){
            if(input[i] == '+' || input[i] == '-' || input[i] == '*'){
                vector<int> left = diffWaysToCompute(input.substr(0, i));
                vector<int> right = diffWaysToCompute(input.substr(i+1));
                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 if(input[i] == '*')
                            res.push_back(l*r);
                    }
                }
            }
        }
        if(res.size() == 0)
            res.push_back(atoi(input.c_str()));
        return res;
    }
};