LeetCode Solutions Blog

Different Ways to Add Parentheses

Number: 241

Difficulty: Medium

Paid? No

Problem Description

Given an expression string containing digits and the operators '+', '-', and '*', the goal is to compute all the different possible results from adding parentheses in all possible ways to change the computation order. The final results, which are guaranteed to fit in a 32-bit integer and will not exceed 10^4 in count, can be returned in any order.

Key Insights

Use recursion to divide the expression at each operator.
Compute results for left and right parts recursively.
Combine the intermediate results using the operator.
Use memoization to store already computed results for subexpressions.
This approach effectively explores all possible parenthesization orders.

Space and Time Complexity

Time Complexity: O(n * 2^n) in the worst-case scenario due to the exponential number of ways to parenthesize. Space Complexity: O(2^n) for the recursion stack and memoization storage in the worst case.

Solution

The solution involves using a recursive divide and conquer strategy. For every operator found in the expression string, we split the string into left and right parts and recursively compute all possible results for both halves. Once we have the results from both sides, we combine them using the current operator. To avoid re-computation, we store the results of already computed sub-expressions in a memoization dictionary. This significantly reduces the computation time when the same subexpression appears multiple times.

Code Solutions

# Define a helper function to compute all possible results for a sub-expression
def diffWaysToCompute(expression):
    # Dictionary to store results for a given sub-expression (Memoization)
    memo = {}
    
    def compute(expr):
        # If result is already computed for sub-expression, return it
        if expr in memo:
            return memo[expr]
        
        results = []
        # Iterate over every character in the sub-expression
        for index, char in enumerate(expr):
            # If the character is an operator, split the expression
            if char in "+-*":
                # Compute possible results for the left part and right part recursively
                left_results = compute(expr[:index])
                right_results = compute(expr[index+1:])
                
                # Combine the results from left and right using the operator
                for left in left_results:
                    for right in right_results:
                        if char == '+':
                            results.append(left + right)
                        elif char == '-':
                            results.append(left - right)
                        elif char == '*':
                            results.append(left * right)
        # If no operator was found, the expression is a number; convert to integer
        if not results:
            results.append(int(expr))
        
        # Store computed results in memo dictionary
        memo[expr] = results
        return results
    
    return compute(expression)

# Example usage:
print(diffWaysToCompute("2-1-1"))