class Solution(object):
    # op1: recursive
    def diffWaysToCompute(self, expression):
        """
        :type expression: str
        :rtype: List[int]
        """
        res = []
        for i, char in enumerate(expression):
            if char in '+-*':
                res1 = self.diffWaysToCompute(expression[:i])
                res2 = self.diffWaysToCompute(expression[i + 1:])
                for n1 in res1:
                    for n2 in res2:
                        if char == '+':
                            res.append(n1 + n2)
                        elif char == '-':
                            res.append(n1 - n2)
                        else:
                            res.append(n1 * n2)
        return res if res else [int(expression)]

    # op2: DP / memoization
    def diffWaysToCompute(self, expression):
        return self.computeWithDP(expression, {})

    def computeWithDP(self, expression, dp):
        res = []
        for i, char in enumerate(expression):
            if char in '+-*':
                s1 = expression[:i]
                res1 = dp[s1] if s1 in dp else self.computeWithDP(s1, dp)
                s2 = expression[i + 1:]
                res2 = dp[s2] if s2 in dp else self.computeWithDP(s2, dp)

                for n1 in res1:
                    for n2 in res2:
                        if char == '+':
                            res.append(n1 + n2)
                        elif char == '-':
                            res.append(n1 - n2)
                        else:
                            res.append(n1 * n2)
        if not res:
            res.append(int(expression))

        dp[expression] = res
        return res

expression = '2-1-1-1-1-1-1-1-1-1-1-1-1'
(Solution().diffWaysToCompute(expression))
