We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Different Ways to Add Parentheses

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires generating all possible outcomes by evaluating different groupings of numbers and operators.
  • Recursion can be utilized to explore all possible ways to partition the expression.
  • Memoization can help optimize repeated calculations for the same sub-expressions.

Space and Time Complexity

Time Complexity: O(N * 2^N) where N is the number of operators, as each operator can create multiple partitions leading to exponential combinations. Space Complexity: O(N) for the recursion stack and memoization storage.

Solution

The solution involves a recursive approach where we evaluate the expression by splitting it at each operator, recursively calculating the results of the left and right sub-expressions. We combine the results based on the operator. To enhance efficiency, we use memoization to store results of previously computed expressions.

Code Solutions

def diffWaysToCompute(expression):
    memo = {}
    
    def compute(expr):
        if expr in memo:
            return memo[expr]
        if expr.isdigit():
            return [int(expr)]
        
        results = []
        for i in range(len(expr)):
            if expr[i] in "+-*":
                left = compute(expr[:i])
                right = compute(expr[i+1:])
                for l in left:
                    for r in right:
                        if expr[i] == '+':
                            results.append(l + r)
                        elif expr[i] == '-':
                            results.append(l - r)
                        elif expr[i] == '*':
                            results.append(l * r)
        memo[expr] = results
        return results

    return compute(expression)
← Back to All Questions