NeetCode #510LC-241MediumBacktracking
← Back to All Problems#510 · #241 · Different Ways to Add Parentheses(为运算表达式设计优先级)
📌 Problem Statement & Constraints
Given a string
expression of numbers and the operators +, -, *, return all possible results from computing all the different ways to parenthesise the expression. Constraints: 1 <= expression.length <= 20; the expression consists of digits and operators; numbers have no leading zeros.💡 Core Algorithmic Approaches
- Divide and conquer on the operators: for each operator, split into a left and a right sub-expression and combine every pair of results.
- A sub-expression with no operator is a single number.
- Memoise the results per sub-expression string (or per index range) to avoid recomputing shared subproblems.
- The number of results is the Catalan number, so the output itself is exponential.
💻 Benchmark Python3 Implementation
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
memo = {}
def dfs(expr: str) -> List[int]:
if expr in memo:
return memo[expr]
res = []
for i, ch in enumerate(expr):
if ch in "+-*": # split at this operator
for l in dfs(expr[:i]):
for r in dfs(expr[i + 1:]):
if ch == "+":
res.append(l + r)
elif ch == "-":
res.append(l - r)
else:
res.append(l * r)
if not res:
res.append(int(expr)) # a pure number
memo[expr] = res
return res
return dfs(expression)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(Catalan(n) * n) where n is the number of operators.
💾 Space Complexity
O(Catalan(n) * n) for the memo table.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the pure-number base case: an expression with no operator must yield its own value.
- Not memoising: the same sub-expression would be recomputed exponentially many times.
- Splitting on digits instead of operators: the split points are exactly the operator positions.
- Trying to handle multi-digit numbers by splitting on characters: the substring slicing handles them naturally.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.