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 *.
Example 1:
Input:"2-1-1"Output:[0, 2]Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2
Example 2:
Input:"2*3-4*5"Output:[-34, -14, -10, -10, 10]Explanation: (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
Approach #1:
namespace studycat {
int add(int x, int y) { return x + y; }
int sub(int x, int y) { return x - y; }
int mul(int x, int y) { return x * y; }
}
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
return helper(input);
}
private:
unordered_map<string, vector<int>> memo;
const vector<int>& helper(const string& input) {
if (memo.count(input)) return memo[input];
vector<int> ans;
for (int i = 0; i < input.length(); ++i) {
char op = input[i];
if (op == ‘+‘ || op == ‘-‘ || op == ‘*‘) {
const string left = input.substr(0, i);
const string right = input.substr(i+1);
const vector<int>& l = helper(left);
const vector<int>& r = helper(right);
std::function<int(int, int)> f;
switch(op) {
case ‘+‘: f = studycat::add; break;
case ‘-‘: f = studycat::sub; break;
case ‘*‘: f = studycat::mul; break;
}
for (int i : l)
for (int j : r)
ans.push_back(f(i, j));
}
}
if (ans.empty())
ans.push_back(std::stoi(input));
memo[input].swap(ans);
return memo[input];
}
};
Analysis:
http://zxi.mytechroad.com/blog/leetcode/leetcode-241-different-ways-to-add-parentheses/
241. Different Ways to Add Parentheses
原文：https://www.cnblogs.com/ruruozhenhao/p/10331475.html