241.md

241. Different Ways to Add Parentheses

Solution 1 (time O(2^n), space O(1))

class Solution(object):
    def diffWaysToCompute(self, expression):
        """
        :type expression: str
        :rtype: List[int]
        """
        if expression.isdigit():
            return [int(expression)]
        
        ans = []
        for i, c in enumerate(expression):
            if c in ["+", "-", "*"]:
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i + 1:])
                for t1 in left:
                    for t2 in right:
                        if c == "+":
                            ans.append(t1 + t2)
                        elif c == "-":
                            ans.append(t1 - t2)
                        else:
                            ans.append(t1 * t2)
        return ans