LC 0241 [M] Different Ways to Add Parentheses - ALawliet/algorithms GitHub Wiki

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
      res = []
      # base case: if the input string is a number, parse and add it to output.
      if '+' not in input and '-' not in input and '*' not in input:
        res.append(int(input))
      else:
        for i in range(len(input)):
          char = input[i]
          if not char.isdigit():
            # break the equation here into two parts and make recursively calls
            prefix, suffix = input[:i], input[i+1:]
            leftParts = self.diffWaysToCompute(prefix)
            rightParts = self.diffWaysToCompute(suffix)
            for part1 in leftParts:
              for part2 in rightParts:
                if char == '+':
                  res.append(part1 + part2)
                elif char == '-':
                  res.append(part1 - part2)
                elif char == '*':
                  res.append(part1 * part2)
      return res