[leetcode]241. Different Ways to Add Parentheses
[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;
}
};