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 <= 20expression consists of digits and the operator '+', '-', and '*'.[0, 99].'-' or '+' denoting the sign.The key idea in #241 Different Ways to Add Parentheses is to evaluate all possible results by changing the grouping of the expression. Instead of evaluating the expression in a single pass, treat each operator (+, -, *) as a potential split point. For every operator, recursively compute all possible results from the left and right sub-expressions and combine them based on the operator.
This naturally forms a divide-and-conquer recursion tree. However, many sub-expressions repeat during recursion, so using memoization (caching results of previously computed substrings) significantly reduces redundant work. A hash map keyed by the substring can store computed results.
The overall complexity grows quickly because the number of valid parenthesizations increases combinatorially. With memoization, the solution efficiently reuses computed sub-results while still exploring all valid expression outcomes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursion (Divide and Conquer) | O(2^n) | O(2^n) |
| Recursion with Memoization | O(n * 2^n) | O(n * 2^n) |
NeetCode
The problem can be approached by using recursion to divide the expression into sub-expressions at each operator, evaluating each possible combination. For each operator, compute the left and right sub-expressions separately, then combine their results based on the operator. This allows us to explore all possible ways to parenthesize the expression and evaluate it.
Time Complexity: O(2^n) - In the worst case, the algorithm evaluates every partition.
Space Complexity: O(2^n) - due to the recursion depth and storage of intermediate results.
1def diffWaysToCompute(expression):
2 if expression.isdigit():
3 return [int(expression)]
4
5 results = []
6 for i, char in enumerate(expression):
7 if char in "+-*":
8 left = diffWaysToCompute(expression[:i])
9 right = diffWaysToCompute(expression[i+1:])
10
11 for l in left:
12 for r in right:
13 if char == '+':
14 results.append(l + r)
15 elif char == '-':
16 results.append(l - r)
17 elif char == '*':
18 results.append(l * r)
19
20 return results
21
22# Example Usage
23print(diffWaysToCompute("2*3-4*5"))This Python solution uses recursion to break down the expression into all possible pairs of sub-expressions partitioned by operators. It recursively computes the result for each pair and combines them according to the operator. The function checks if the expression is a single number and returns it as a list; otherwise, it iterates through the expression characters, recursively calls itself for partitions, and calculates possible results.
To optimize the recursive approach, we can use memoization to cache the results of subproblems. This avoids redundant evaluations of the same sub-expressions, thereby optimizing the time complexity. We store results of sub-expressions in a hash map and reuse them when the same sub-expression is encountered again.
Time Complexity: O(n^3) - n^2 subproblems with evaluation cost per subproblem.
Space Complexity: O(n^2) - for storing results of subproblems in a memoization table.
1import java.util.*;
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar expression evaluation problems are asked in technical interviews at companies like Google, Amazon, and Meta. It tests recursion, divide-and-conquer thinking, and optimization using memoization.
A hash map (dictionary) is commonly used for memoization, where the key is the substring of the expression and the value is the list of computed results. This helps reuse results for repeated sub-expressions during recursion.
Many sub-expressions appear multiple times during recursive splitting. Memoization stores the results of these sub-expressions so they don't need to be recomputed, significantly improving performance.
The optimal approach uses divide-and-conquer recursion combined with memoization. Each operator is treated as a split point, and results from left and right sub-expressions are combined. Memoization stores results of previously computed substrings to avoid redundant calculations.
The Java version applies memoization by storing results of already computed sub-expressions in a HashMap. It checks for cached results before computing new ones, ensuring no duplicate calculations for the same expression parts. This optimization reduces the time complexity significantly compared to the naive recursive approach.