Different Ways to Add Parentheses
#349 Most AskedMedium
Different Ways to Add Parentheses #349 Most Asked
Medium
2 views
Topics:
RecursionDynamic Programming
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.
The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 104.
Example 1:
Input: expression = "2-1-1" Output: [0,2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2
Example 2:
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 <= 20expressionconsists of digits and the operator'+','-', and'*'.- All the integer values in the input expression are in the range
[0, 99]. - The integer values in the input expression do not have a leading
'-'or'+'denoting the sign.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the range of values for the numbers in the expression? Can they be negative?
- Can the input string be empty or null? If so, what should I return?
- What operators are allowed in the input string, and is the expression guaranteed to be syntactically valid (e.g., no consecutive operators or numbers)?
- Is the order of the results in the returned list important?
- Should I handle integer overflow? If so, what should the behavior be?
Brute Force Solution
Approach
The problem asks us to find all the possible results of an arithmetic expression by grouping parts of it with parentheses in different ways. The brute force strategy is simple: we try every single possible way to add parentheses to the expression.
Here's how the algorithm would work step-by-step:
- Consider the expression as a whole.
- Find each operator (like plus, minus, multiply) in the expression.
- For each operator, imagine putting a pair of parentheses around the parts of the expression on either side of it.
- This splits the problem into two smaller problems: finding all the results of the expression to the left of the operator and all the results of the expression to the right of the operator.
- Solve each of those smaller problems in the same way: by trying all possible ways to add parentheses within them.
- Once you have all the possible results for the left and right sides, combine them using the operator you started with. For example, if you are considering a plus sign, add all the possible left results to all the possible right results.
- Repeat this process for every operator in the original expression, and for every sub-expression you create.
- Keep track of all the different results you get from all the different ways of adding parentheses.
- In the end, you'll have a list of all the possible results of the expression.
Code Implementation
def different_ways_to_add_parentheses(expression):
# If the expression is just a number, return it as an integer.
if expression.isdigit():
return [int(expression)]
results = []
for index, character in enumerate(expression):
# Find each operator in the expression.
if character in ['+', '-', '*']:
# Recursively compute results for left and right subexpressions.
left_results = different_ways_to_add_parentheses(expression[:index])
right_results = different_ways_to_add_parentheses(expression[index+1:])
# Combine the results from the left and right.
for left_result in left_results:
for right_result in right_results:
if character == '+':
results.append(left_result + right_result)
elif character == '-':
results.append(left_result - right_result)
elif character == '*':
results.append(left_result * right_result)
return resultsBig(O) Analysis
Time Complexity
O(C_n) – Let n be the number of operators in the expression. The algorithm explores all possible ways to parenthesize the expression. The number of ways to parenthesize an expression with n operators is given by the nth Catalan number, denoted as C_n. For each possible parenthesization, we perform O(n) operations to evaluate the expression (since there are n operators). Therefore, the time complexity is proportional to n times the nth Catalan Number. Since Catalan numbers grow faster than exponentially, the time complexity is O(C_n) where C_n represents the nth catalan number which is approximately 4^n / (n * sqrt(n)). In the context of the prompt's description this equates to trying all the possible ways to put the parenthesis in the expression. The final result will then be the cartesian product of all the computed intermediate values.
Space Complexity
O(N) – The algorithm uses recursion. In the worst-case scenario, such as an expression like '1+1+1+1...', the recursion depth can reach N-1, where N is the number of operands (or the length of the expression). Each recursive call consumes stack space. Furthermore, each recursive call creates lists to store the results of the left and right subexpressions which, in total, can grow to be proportional to the input size N. Therefore, the auxiliary space used by the recursion stack and intermediate result lists is O(N).
Optimal Solution
Approach
The goal is to explore every possible way to insert parentheses into an expression and calculate the result. We'll use a method where we break down the problem into smaller, self-similar subproblems and combine their results to find all final answers.
Here's how the algorithm would work step-by-step:
- Look at the expression. Find an operator, like plus or minus, within it.
- Imagine that operator is the last one you'll perform. Split the expression into two smaller expressions on either side of that operator.
- Now, do the same thing for each of those smaller expressions: find an operator within them and split them into even smaller expressions.
- Keep doing this until you can't split the expressions anymore, meaning you're left with just single numbers.
- Calculate the value of the smallest expressions (the single numbers).
- Work your way back up. For each operator you split on, take all the possible results from its left and right sides, and combine them using that operator.
- Keep combining the results as you go back up the splits, until you have a list of all the possible final results for the entire original expression. Each result represents a different way of adding parentheses.
Code Implementation
def different_ways_to_add_parentheses(input_expression):
# If the input is a number, return it as a single-element list.
if input_expression.isdigit():
return [int(input_expression)]
results = []
for index, character in enumerate(input_expression):
if character in ['+', '-', '*']:
# Split the expression into two sub-expressions
left_sub_expression = input_expression[:index]
right_sub_expression = input_expression[index + 1:]
# Recursively calculate results for sub-expressions
left_results = different_ways_to_add_parentheses(left_sub_expression)
right_results = different_ways_to_add_parentheses(right_sub_expression)
# Combine results from left and right sub-expressions
for left_result in left_results:
for right_result in right_results:
if character == '+':
results.append(left_result + right_result)
elif character == '-':
results.append(left_result - right_result)
else:
results.append(left_result * right_result)
return resultsBig(O) Analysis
Time Complexity
O(C_n) – The time complexity of this algorithm is dictated by the number of ways to parenthesize the expression. Let n be the number of operators in the expression. The algorithm recursively splits the expression at each operator. The number of ways to parenthesize an expression with n operators is given by the Catalan number C_n = (2n)! / ((n+1)! * n!). Therefore, the time complexity is proportional to the nth Catalan number since we explore all possible parenthesizations. Because each split requires combining results from left and right sub-expressions, the total operations grow according to the Catalan number sequence. The time complexity reflects the exponential growth inherent in exploring all possible combinations of parentheses.
Space Complexity
O(N) – The algorithm uses recursion. In the worst-case scenario, the expression consists of only numbers and operators that allow full binary tree formation. This leads to a maximum recursion depth proportional to the number of operators, which is related to the number of numbers, N, in the input expression. Each recursive call consumes stack space, resulting in auxiliary space usage of O(N) due to the call stack. Additionally, temporary lists are created at each level to store intermediate results from left and right sub-expressions. While the size of these lists varies, the total memory consumed across all levels remains within a O(N) bound, where N is the length of the input string.
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty input string | Return an empty list if the input string is null or empty, as there are no expressions to evaluate. |
| Input string containing only a single number | Return a list containing the single number as an integer, since there are no operations to perform. |
| Input string with only one operator and two numbers (e.g., '1+2') | Evaluate the simple expression directly and return a list containing the single result. |
| Input string with leading/trailing whitespace | Trim the input string to remove any leading or trailing whitespace before processing to avoid parsing errors. |
| Input string with very large numbers that could lead to integer overflow | Use long integer data type to store intermediate results and final answers to prevent integer overflow, and check for potential overflows during calculations. |
| Input string with a large number of operators and operands (potential stack overflow with naive recursion) | Implement memoization to store intermediate results and avoid redundant calculations, improving efficiency and reducing stack depth. |
| Input with negative numbers or negative intermediate results | The parsing and evaluation logic should correctly handle negative numbers and intermediate results during calculations. |
| Input containing only multiplication with zero e.g. '0*0*0' | The solution needs to handle multiplication with zero correctly, returning 0 as the only possible result. |
Null or empty input string
How to Handle:
Return an empty list if the input string is null or empty, as there are no expressions to evaluate.
Input string containing only a single number
How to Handle:
Return a list containing the single number as an integer, since there are no operations to perform.
Input string with only one operator and two numbers (e.g., '1+2')
How to Handle:
Evaluate the simple expression directly and return a list containing the single result.
Input string with leading/trailing whitespace
How to Handle:
Trim the input string to remove any leading or trailing whitespace before processing to avoid parsing errors.
Input string with very large numbers that could lead to integer overflow
How to Handle:
Use long integer data type to store intermediate results and final answers to prevent integer overflow, and check for potential overflows during calculations.
Input string with a large number of operators and operands (potential stack overflow with naive recursion)
How to Handle:
Implement memoization to store intermediate results and avoid redundant calculations, improving efficiency and reducing stack depth.
Input with negative numbers or negative intermediate results
How to Handle:
The parsing and evaluation logic should correctly handle negative numbers and intermediate results during calculations.
Input containing only multiplication with zero e.g. '0*0*0'
How to Handle:
The solution needs to handle multiplication with zero correctly, returning 0 as the only possible result.
0/1037 Bloomberg LP questions completed
0/1037 completed
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
