241.Different Ways to Add Parentheses - leetcode

241. Different Ways to Add Parentheses

Idea

1. This algorithm divides inp string by operators.
   • each operator is a dividing point, so reculsively call all possible cases.

      for i in range(len(inp)):
       if not self.match(inp[i]):
           continue
       left = self.diffWaysToCompute(inp[:i])
       right = self.diffWaysToCompute(inp[i+1:])
     

2. From reculsive calling, If we get the left and right results, merge the results.
   • all possible combinataions are generated.

      for i in range(len(inp)):
       ...
       operator = inp[i]
       for l in left:
           for r in right:
               res.append(self.op(operator, l, r))
     

3. Base cases can be occured when left or right are empty.

    if not bool(res):
        return [int(inp)]
   

In [1]:

class Solution(object):
    def __init__(self):
        self.match = lambda c: True if c in ['+', '-', '*'] else False
    def op(self, o, a, b):
        if o == '+':
            return a + b
        elif o == '-':
            return a - b
        elif o == '*':
            return a * b
        assert o, 'invalid'
    def diffWaysToCompute(self, inp):
        """
        :type inp: str
        :rtype: List[int]
        """
        res = []
        for i in range(len(inp)):
            if not self.match(inp[i]):
                continue
            left = self.diffWaysToCompute(inp[:i])
            right = self.diffWaysToCompute(inp[i+1:])
            operator = inp[i]
            for l in left:
                for r in right:
                    res.append(self.op(operator, l, r))
        if not bool(res):
            return [int(inp)]
        return sorted(res)

In [2]:

inp = "2*3-4*5"
sol = Solution()
sol.diffWaysToCompute(inp)

[-34, -14, -10, -10, 10]

referenece

discuss