241. Different Ways to Add Parentheses
Model: qwen3.5:9b
Topics: Divide and Conquer
FAANG asked: 0
Acceptance rate: 57.6%
Problem Breakdown
We are given a string representing an arithmetic expression containing single-digit numbers (though the logic generalizes to multi-digits), and operators +, -, or *. The goal is to compute all possible results by inserting parentheses in different valid ways. Essentially, we need to explore every binary tree structure where leaves are operands and internal nodes are operators.
Inputs: A string expression containing digits and one of three operators (+, -, *).
Outputs: A list of integers representing the result for each unique parenthesization order. Note that if different groupings yield the same numerical value, we must include both in the output (as seen in Example 2).
Implicit Constraints & Edge Cases:
- Single Operand: If there are no operators (e.g.,
"5"), it’s a base case returning[int("5")]. - Multi-digit Numbers: While examples show single digits, the string could theoretically contain multi-digit numbers like
10+20. My parsing logic must handle extracting full integer values from substrings correctly when splitting at an operator. - Negative Results: Subtraction can yield negative integers; Python handles this natively without special handling for overflow (unlike C++/Java).
Intuition
If we try to solve this iteratively or with simple recursion, we quickly realize that the same sub-expressions get computed repeatedly. For example, in 2*3-4*5, calculating (2*(3-(4*5))) involves computing 3-(4*5). Later, if another branch requires a similar structure (though less likely here), or simply because we are exploring different split points for the same substring range, redundant work occurs.
The core insight is Divide and Conquer. Any expression can be viewed as:
Left Operand + Operator + Right Operand
We iterate through every operator in the string to treat it as the “root” of a binary tree operation at that step. We recursively solve for everything to its left, then everything to its right.
However, since we are solving sub-problems on substrings (e.g., expression[0:3]), and these substrings appear in multiple recursive calls depending on where the outer operator is chosen, this exhibits overlapping subproblems. This screams for Memoization or Dynamic Programming. We should cache results based on the substring range to avoid re-computing them.
Approach
I will implement a top-down recursion with memoization (Top-Down DP).
- Define a helper function
solve(start, end)that returns all possible integer values for the sub-expression defined by indicesstartandend. - Base Case: If there are no operators between
startandend, parse the substring as an integer and return it in a list[int_val]. - Recursive Step: Iterate through every character index from
starttoend-1. Check if the current char is an operator (+,-, or*). - If we find an operator at index
i:- Recursively call
solve(start, i)for the left part (exclusive of op). - Recursively call
solve(i + 1, end)for the right part (inclusive of next char after op).
- Recursively call
- Combine: For every value in the left list and every value in the right list, apply the operator at index
ito generate a new result. Add this to our current results set. - Memoization: Store the computed list for
(start, end)before returning it so future calls with these indices return instantly from cache.
Complexity Analysis
- Time Complexity: or more precisely proportional to the Catalan number of operators (). Since we must generate all possible results and there are exponentially many ways to parenthesize an expression, the output size itself is exponential in terms of operator count. The work done per split point is linear relative to result lists sizes. Given
expression.length <= 20, this fits well within time limits (roughly worst case operations). - Space Complexity: for the memoization table storing results for all substring ranges, plus recursion stack depth of .
Solution
from typing import List
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
# Memoization cache to store results for specific substrings (start_index, end_index)
memo = {}
def solve(start: int, end: int) -> List[int]:
# Check if result is already computed and cached
key = f"{start}:{end}"
if key in memo:
return memo[key]
results = []
# Iterate through the substring to find operators.
# We look at indices from start up to end-1 (inclusive).
for i in range(start, len(expression)):
char = expression[i]
if char == '+' or char == '-' or char == '*':
# Split into left and right parts based on current operator index 'i'
# Left part: start to i-1 (inclusive) -> slice [start:i]
# Right part: i+1 to end (inclusive) -> slice [i+1:end+1]
# Note: We need the actual substring content for recursive calls.
# To avoid slicing overhead in key generation, we pass indices here but use expression string globally.
left_results = solve(start, i - 1) if start <= i else []
right_results = solve(i + 2, end) if i < len(expression) - 1 and not (i == len(expression)-1) else []
# Wait, the slicing logic above is slightly messy with indices.
# Let's refine: Left range [start, i-1], Right range [i+1, end].
# If we are at index 'i' which is an operator:
left_part = expression[start:i] if start < i else ""
right_part = expression[i+1:end+1] if i + 1 <= end else ""
# Actually simpler logic for recursion indices:
# Left sub-problem covers range [start, i-1].
# Right sub-problem covers range [i+2, end]? No.
# Let's stick to standard slicing approach inside the function or careful index passing.
# Given constraints (len <= 20), string slicing is acceptable for clarity in interview code unless strict perf needed.
pass
return results
# Refined Implementation with clean indices logic:
def get_results(start_idx, end_idx):
if start_idx > end_idx:
return []
sub_expr = expression[start_idx : end_idx + 1]
key = (start_idx, end_idx)
if key in memo:
return memo[key]
# Base case: No operators found in this substring range.
# We check for presence of operator by iterating or checking sub_expr directly?
# Iterating is safer to handle multi-digit numbers correctly without regex overhead, though simple scan works.
has_op = False
# If we can parse the whole thing as a number (no ops), return it immediately.
if not any(c in '+-*' for c in sub_expr):
memo[key] = [int(sub_expr)]
return memo[key]
results = []
# Iterate through indices of this specific substring to find operators
# We need absolute indices from original expression string though.
# Let's use the global 'expression' and pass start/end inclusive bounds relative to it.
for i in range(start_idx, end_idx + 1):
if expression[i] in '+-*':
left_vals = get_results(start_idx, i - 1)
right_vals = get_results(i + 1, end_idx)
op_char = expression[i]
for l_val in left_vals:
for r_val in right_vals:
if op_char == '+': results.append(l_val + r_val)
elif op_char == '-': results.append(l_val - r_val)
elif op_char == '*': results.append(l_val * r_val)
memo[key] = results
return results
# Initial call covering the whole string (inclusive indices 0 to len-1)
full_results = get_results(0, len(expression) - 1)
return full_results
Edge Cases Handled
- Single Number: The base case
if not any(c in '+-*' ...)handles strings like"5"or"123", returning[int(sub_expr)]. - Duplicate Results: Since we iterate through all operators and combine lists without deduplication, if two different parenthesizations yield the same number (e.g.,
((2-1)-1)vs(2-(1-1))in some contexts), both are added to the list. This matches Example 2 requirements where duplicates exist in output. - Negative Integers: Python’s integer arithmetic handles negative results from subtraction automatically without overflow issues (unlike fixed-width types).