317. Bracket Every Way
A calculator game shows an expression made of non-negative whole numbers joined by the operators +, - and *, with no spaces. The player may place brackets anywhere to decide which operation is carried out first, and different bracketings can give different results.
Return the results of every possible way of fully bracketing the expression, one value for each distinct bracketing (so equal results can appear more than once), sorted in ascending order. An expression with a single number has exactly one result: that number. Splitting the expression at each operator and combining the results of both sides is the natural approach; remember the results of sub-expressions you have already solved.
Example 1
- Input:
- expression = "4-3*2"
- Output:
- [-2,2]
- Explanation:
Bracketing as (4-3)*2 gives 2 and as 4-(3*2) gives -2, so the sorted answer is [-2, 2].
Example 2
- Input:
- expression = "2*3-4+1"
- Output:
- [-4,-1,0,1,3]
- Explanation:
There are five bracketings, with results 3, 1, -1, 0 and -4; sorted they give [-4, -1, 0, 1, 3].
Constraints
1 ≤ expression.length ≤ 30
The expression has at most 7 numbers, each between 0 and 20 (written in decimal without leading zeros), separated by +, - or *.
Every result fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(C(n) * n)
- Space
- O(C(n) * n)