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".
|
1 2 |
((2-1)-1) = 0 (2-(1-1)) = 2 |
Output: [0, 2]
Example 2:
Input: "2*3-4*5"
|
1 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: [-34, -14, -10, -10, 10]
Solution:
Running time: 3ms
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
// Author: Huahua namespace huahua { int add(int a, int b) { return a+b; } int minus(int a, int b) { return a-b; } int multiply(int a, int b) { return a*b; } } // namespace huahua class Solution { public: vector<int> diffWaysToCompute(string input) { return ways(input); } private: const vector<int>& ways(const string& input) { // Already solved, return the answer if(m_.count(input)) return m_[input]; // Array for answer of input vector<int> ans; // Break the expression at every operator for(int i=0;i<input.length();++i) { char op = input[i]; // Split the input by an op if(op=='+' || op=='-' || op=='*') { const string left = input.substr(0, i); const string right = input.substr(i+1); // Get the solution of left/right sub-expressions const vector<int>& l = ways(left); const vector<int>& r = ways(right); std::function<int(int,int)> f; switch(op) { case '+': f = huahua::add; break; case '-': f = huahua::minus; break; case '*': f = huahua::multiply; break; } // Combine the solution for(int a : l) for(int b : r) ans.push_back(f(a,b)); } } // Single number, e.g. s = "3" if(ans.empty()) ans.push_back(std::stoi(input)); // memorize the answer for input m_[input].swap(ans); return m_[input]; } unordered_map<string, vector<int>> m_; }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Author: Huahua, 44 ms class Solution: def diffWaysToCompute(self, input): ops = {'+': lambda x, y: x + y, '-': lambda x, y: x - y, '*': lambda x, y: x * y} def ways(s): ans = [] for i in range(len(s)): if s[i] in "+-*": ans += [ops[s[i]](l, r) for l, r in itertools.product(ways(s[0:i]), ways(s[i+1:]))] if not ans: ans.append(int(s)) return ans return ways(input) |