Different Ways To Add Parentheses Problem
Description
LeetCode Problem 241.
Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.
Example 1:
1
2
3
4
5
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
1
2
3
4
5
6
7
8
Input: expression = "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
Constraints:
- 1 <= expression.length <= 20
- expression consists of digits and the operator ‘+’, ‘-‘, and ‘*’.
- All the integer values in the input expression are in the range [0, 99].
Sample C++ Code
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
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> result;
int size = input.size();
for (int i = 0; i < size; i++) {
char cur = input[i];
if (cur == '+' || cur == '-' || cur == '*') {
// Split input string into two parts and solve them recursively
vector<int> result1 = diffWaysToCompute(input.substr(0, i));
vector<int> result2 = diffWaysToCompute(input.substr(i+1));
for (auto n1 : result1) {
for (auto n2 : result2) {
if (cur == '+')
result.push_back(n1 + n2);
else if (cur == '-')
result.push_back(n1 - n2);
else
result.push_back(n1 * n2);
}
}
}
}
// if the input string contains only number
if (result.empty())
result.push_back(atoi(input.c_str()));
return result;
}
};