LeetCode 241: Different Ways to Add Parentheses Solution in Python – A Step-by-Step Guide

What Is LeetCode 241: Different Ways to Add Parentheses?

In LeetCode 241: Different Ways to Add Parentheses, you’re given a string expression containing numbers and operators (+, -, *). Your task is to return a list of all possible results by adding parentheses to change the order of operations. This problem is a twist on string manipulation challenges like LeetCode 3: Longest Substring Without Repeating Characters, focusing on computational creativity rather than substring hunting.

Problem Statement

• Input: A string expression with digits and operators (+, -, *).
• Output: A list of integers representing all possible results from different parenthesizations.
• Rules: Evaluate the expression following standard operator precedence (multiplication before addition/subtraction), altered by parentheses.

Constraints

• Expression length: 1 to 20 characters.
• Numbers: 0 to 9 (single digits).
• Operators: +, -, * only.
• Results fit within a 32-bit integer.

Examples

• Input: "2-5"
• Possible ways: (2-5)
• Output: [-3]
• Input: "2*3-4"
• Possible ways: (2*3)-4, 2*(3-4)
• Output: [2, -2]
• Input: "2-5+3"
• Possible ways: (2-5)+3, 2-(5+3)
• Output: [0, -6]

Understanding the Problem: Parentheses and Possibilities

To solve LeetCode 241: Different Ways to Add Parentheses in Python, we need to generate all possible results by grouping operations with parentheses. A naive approach—manually listing every combination—becomes impractical fast. Instead, we’ll use two strategies: 1. Best Solution (Divide-and-Conquer): O(n * 2^n) time—efficient and elegant. 2. Alternative Solution (Brute Force with Validation): O(2^n) combinations with evaluation—simpler but less optimized.

Let’s start with the best solution.

Best Solution: Divide-and-Conquer Approach

Why This Is the Best Solution

The divide-and-conquer approach is the top pick for LeetCode 241 because it breaks the problem into smaller subproblems, solving them efficiently and avoiding redundant calculations with memoization potential. It’s a smart way to handle expressions, making it both fast and scalable for the constraints.

How It Works

• Split the expression at each operator into left and right parts.
• Recursively compute all possible results for the left and right parts.
• Combine these results using the operator at the split point.
• If no operators are present, return the number as a single-element list.

Step-by-Step Example

Example: expression = "2*3-4"

• Step 1: Split at * → "2" and "3-4"
• Left: "2" → [2]
• Right: "3-4"
• Split at - → "3" and "4"
• Left: "3" → [3]
• Right: "4" → [4]
• Combine with -: [3-4] → [-1]
• Combine with *: [2*-1] → [-2]
• Step 2: Split at - → "2*3" and "4"
• Left: "2*3"
• Split at * → "2" and "3"
• Left: "2" → [2]
• Right: "3" → [3]
• Combine with *: [2*3] → [6]
• Right: "4" → [4]
• Combine with -: [6-4] → [2]
• Output: [-2, 2]

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy codeclass Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        # Step 1: Define operator computation
        def compute(left_results, right_results, op):
            results = []
            for l in left_results:
                for r in right_results:
                    if op == '+':
                        results.append(l + r)
                    elif op == '-':
                        results.append(l - r)
                    elif op == '*':
                        results.append(l * r)
            return results

        # Step 2: Base case - pure number
        if expression.isdigit():
            return [int(expression)]

        # Step 3: Process the expression
        results = []
        for i, char in enumerate(expression):
            if char in {'+', '-', '*'}:
                # Split into left and right parts
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i+1:])
                # Combine results with the operator
                results.extend(compute(left, right, char))

        # Step 4: Return all possible results
        return results

• Time Complexity: O(n * 2^n)—exponential due to splitting at each operator, but optimized by subproblem reuse.
• Space Complexity: O(2^n)—storing all possible results.

This method’s divide-and-conquer logic is a game-changer.

Alternative Solution: Brute Force with Validation

Why an Alternative Approach?

The brute force with validation approach generates all possible parenthesized expressions and evaluates them. It’s less efficient but easier to conceptualize for beginners, offering a hands-on way to see how parentheses affect outcomes.

How It Works

• Identify all possible ways to insert parentheses by splitting at operators.
• Manually construct and evaluate each valid expression.
• Use a helper to compute the final value of each.

Step-by-Step Example

Example: expression = "2*3-4"

• Way 1: (2*3)-4
• Compute: 2*3 = 6, 6-4 = 2
• Way 2: 2*(3-4)
• Compute: 3-4 = -1, 2*-1 = -2
• Output: [2, -2]

Code for Brute Force Approach

Copy codeclass Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        # Step 1: Helper to evaluate a simple expression
        def evaluate(expr):
            stack = []
            num = 0
            op = '+'
            for char in expr + '+':
                if char.isdigit():
                    num = num * 10 + int(char)
                elif char in {'+', '-', '*'}:
                    if op == '+':
                        stack.append(num)
                    elif op == '-':
                        stack.append(-num)
                    elif op == '*':
                        stack.append(stack.pop() * num)
                    num = 0
                    op = char
            return sum(stack)

        # Step 2: Generate all parenthesized expressions
        def generate_expressions(expr):
            if expr.isdigit():
                return [int(expr)]
            results = set()
            for i, char in enumerate(expr):
                if char in {'+', '-', '*'}:
                    left = generate_expressions(expr[:i])
                    right = generate_expressions(expr[i+1:])
                    for l in left:
                        for r in right:
                            if char == '+':
                                results.add(l + r)
                            elif char == '-':
                                results.add(l - r)
                            elif char == '*':
                                results.add(l * r)
            return list(results)

        # Step 3: Return results
        return generate_expressions(expression)

• Time Complexity: O(2^n)—exponential due to all combinations.
• Space Complexity: O(2^n)—storing unique results.

It’s intuitive but less efficient.

Comparing the Two Solutions

• Best Solution (Divide-and-Conquer):
• Pros: Optimized, scalable, elegant.
• Cons: Requires understanding of recursion.
• Alternative Solution (Brute Force):
• Pros: Simple concept, visible steps.
• Cons: Slower, redundant evaluations.

The divide-and-conquer method shines brighter.

Additional Examples and Edge Cases

Single Number

• Input: "5"
• Output: [5]

Two Operands

• Input: "2+3"
• Output: [5]

Complex Case

• Input: "1+2*3"
• Output: [7, 9] ((1+2)*3, 1+(2*3))

Both solutions handle these well.

Complexity Breakdown

• Divide-and-Conquer:
• Time: O(n * 2^n)—exponential but efficient.
• Space: O(2^n)—for results.
• Brute Force:
• Time: O(2^n)—slower evaluation.
• Space: O(2^n)—similar storage.

Divide-and-conquer takes the lead.

Key Takeaways for Beginners

• Divide-and-Conquer: Break problems into manageable chunks.
• Parentheses Power: Change operation order creatively.
• Brute Force: Good for learning, less for speed.
• Python Tip: String slicing rocks—see [Python Basics](/python/basics).

Final Thoughts: Parenthesize Like a Pro

LeetCode 241: Different Ways to Add Parentheses in Python is a fun twist on expression evaluation. The divide-and-conquer solution offers brilliance, while brute force provides clarity. Want more? Try LeetCode 224: Basic Calculator or LeetCode 227: Basic Calculator II. Ready to compute? Head to Solve LeetCode 241 on LeetCode and explore those possibilities today!