241.md

241 Different Ways to Add Parentheses

Description

link

---

Solution

See Code

---

Code

O(n^2)

class Solution:
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        if input.isdigit():
            return [int(input)]
        
        res = []
        for i in range(len(input)):
            if input[i] in '+-*':
                pre = self.diffWaysToCompute(input[:i])
                suc = self.diffWaysToCompute(input[i + 1:])
                for pr in pre:
                    for su in suc:
                        res.append(self.helper(pr, su, input[i]))
            else:
                pass
        return res
    
    def helper(self, pr, su, op):
        pr, su = int(pr), int(su)
        if op == '+':
            return pr + su
        if op == '-':
            return pr - su
        if op == '*':
            return pr * su