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
Example 1+
,-
and *
.
Input:
"2-1-1"
.((2-1)-1) = 0 (2-(1-1)) = 2
Output:
Example 2[0, 2]
Input:
"2*3-4*5"
(2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10
Output:
A: 分而治之, 从每个+-* 拆开[-34, -14, -10, -10, 10]
class Solution { public: vector<int> diffWaysToCompute(string input) { // assume no space bool foundOp = false; vector<int> res; for(int i =0;i<input.size();i++){ if(!isdigit(input[i])){ foundOp=true; auto L=diffWaysToCompute(input.substr(0,i)); auto R=diffWaysToCompute(input.substr(i+1)); for(auto s1 : L) for(auto s2 : R) res.push_back(cal(s1, s2, input[i])); } } if(not foundOp) res.push_back(stoi(input)); return res; } private: int cal(int a, int b, char op){ if(op=='+') return a+b; if(op=='-') return a-b; if(op=='*') return a*b; return 0; // wrong . should never hit } };
Mistakes:
一开始,先split成一个个vector<string> 其实是没有必要的。 以后注意
No comments:
Post a Comment