Different Ways to Add Parentheses - Medium - L
Published:
Question
- https://leetcode.com/problems/different-ways-to-add-parentheses/
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.
Approach
- Recursive Algorithm
Solution
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
// Typical recursion problem.
if (input.find('+') == string::npos && input.find('-') == string::npos && input.find('*') == string::npos)
{
return {stoi(input)}; // base case, input string is numeric
}
int size = input.size();
vector<int> vals;
for (int i = 0; i < size; ++i)
{
while (i < size && input[i] <= '9' && input[i] >= '0')
{
++i; // find the operator
}
if (i >= size)
{
break; // reach the end
}
char op = input[i];
vector<int> v1 = diffWaysToCompute(input.substr(0, i)); // recursively calculate the value in previous parenthesis
vector<int> v2 = diffWaysToCompute(input.substr(i + 1)); // recursively calculate the value in next parenthesis
for (int n1 : v1)
{
for (int n2 : v2)
{
int val = op == '+' ? n1 + n2 : op == '-' ? n1 - n2 : n1 * n2;
vals.push_back(val);
}
}
}
return vals;
}
};