Leetcode Daily Question 19/09/2024 - 241. Different Ways to Add Parentheses

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. The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 104.

Solution: ►

from typing import List
class Solution:
  def __init__(self):
    self.memo = {}
  
  def dfs(self, exp: str) -> List[int]:
    if exp.isdigit():
      return [int(exp)]
    
    if exp in self.memo:
      return self.memo[exp]
    
    result = []
    
    for i, char in enumerate(exp):
      if char in "+-*":
    	left_exp = self.dfs(exp[:i])
    	right_exp = self.dfs(exp[i+1:])
        
        for left in left_exp:
          for right in right_exp:
            if char == "+":
              result.append(left + right)
            elif char == "-":
              result.append(left - right)
            elif char == "*":
              result.append(left * right)
    
    self.memo[exp] = result
    return result
  
  
  def diffWaysToCompute(self, expression: str) -> List[int]:
    return self.dfs(expression)

Explanation:

We can solve this by dfs. The idea is continuously explore and divide subexpression to calculate possible results given the operators.

This is best visualised with an example. Consider the expression "2*3-4*5".

First, we encounter "*" at index 1 of the original expression.
We split the expression into left_exp = "2" and right_exp = "3-4*5"
Now left_exp is just a number so we can return [2] for computation later.
We can further split right_exp into "3" and "4*5" as we hit "-" at index 1 of right_exp
	- "3" returns [3]
  	- "4*5" splits into "4" "5"
    	- returns [4] [5]
Now we comptute 4 * 5 = 20,
then 3 - 20 = -17
then 2 * (-17) = -34
and append this to result as well as memo to mark this particular expression as seen

Then, we encounter "-" at index 3 of the originl expression.
We split the expression into "2*3" and "4*5"
We further split "2*3" into "2" "3" and return [2] [3]
"4*5" into "4" "5" and return [4] [5]
We then calculate 4 * 5 = 20
2 * 3 = 6
6 - 20 = -14 and append this to result and mark it as seen.

Continuing like this, we can search through every possible partition and result.

So lets write this into code. First, we define a dictionary to memorise seen expressions and results.

def __init__(self):
  self.memo = {}

Then we can define the dfs function.

def dfs(self, exp):
  if exp.isdigit():
    return [int(exp)] #If the expression is say just "2" then we return [2] for calculation later
  
  if exp in self.memo:
    return self.memo[exp] # If we have seen this exp before we already know what the result is
  
  result = [] #This keeps track of the result of the expression.
  
  for i, char in enumerate(exp): # We need index to know where to split exp.
    if char in "+-*": # If we hit an operator
      left_exp = self.dfs(exp[:i])
      right_exp = self.dfs(exp[i+1:]) 
      for left in left_exp:
        for right in right_exp:
          if char == "+": # At this point we would have two arrs with only a single integer in each.
            result.append(left + right) 
          elif char == "-":
            result.append(left - right)
          elif char == "*":
            result.append(left * right)
            
  self.memo[exp] = result
  return result

Finally, we use this to calculate the desired result

def diffWaysToCompute(self, expression):
  return self.dfs(expression)

The time complexity is exponential. Since with n operands, we need to iterate through n-1 operands. Each operand requires us to possibly split the expression and consider subexpressions. So the time complexity is approximately O(4^n) where n is length of expression, this is obtained from the Catalan number C(n-1).

Hence the space complexity is also O(4^n) as we store every unique expression seen in memoery.

The full solution can be found near the top of the page.

For those interested. The Catalan Number is a combinatoric expression describing partitions. It has form 
1/(n+1)(2n C n) = 2n! / (n+1)! n!,
where C is the CHOOSE operator in combinatorics. 
One can read more about Catalan Number at https://brilliant.org/wiki/catalan-numbers/.

Back