Medium

Different Ways to Add Parentheses

LAB

Return all possible results from computing the arithmetic expression with different parenthesization, sorted ascending.

EXAMPLES

Example 1

Input
{
  "expression": "2-1-1"
}

Output
[
  0,
  2
]

FUNCTION SHAPE

expression: string→intArray

SOLUTION NOTE

Divide and conquer with memoization. Split at each operator, compute all combinations of left and right results.

Reveal reference solution +

pythonREFERENCE

def diffWaysToCompute(self, expression: str) -> List[int]:
    @cache
    def dp(s):
        if s.isdigit():
            return [int(s)]

        res = []
        for i, c in enumerate(s):
            if c in '+-*':
                left = dp(s[:i])
                right = dp(s[i+1:])
                for l in left:
                    for r in right:
                        if c == '+':
                            res.append(l + r)
                        elif c == '-':
                            res.append(l - r)
                        else:
                            res.append(l * r)
        return res

    return dp(expression)

TimeO(n × 2^n)

SpaceO(2^n)

Open on LeetCode ↗