241. Different Ways to Add Parentheses

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        """tc  O()???
        main idea: devide & conquer  + memoization 
                1. each time encounter a  operator, devide into left and right part, do recursion to get a list of integer, 
                2. iterate through left and right  make new substring with different priority that brought from parathesis
                3. early termination:   (1) when substring has only digit, return number (2) when substring exist in memo, return 
        """
        memo = {}
        def dfs(s,memo):
            if s in memo:
                return memo[s]
            if s.isdigit():
                # update memo since its not seen 
                memo[s] = [int(s)]
                return [int(s)]
            res = []
            for i,c in enumerate(s):
                if c in ['+','-','*']:
                    left = dfs(s[:i],memo) # return a list of integer???  
                    right = dfs(s[i+1:],memo)
                    for l in left:
                        for r in right:
                            if c == '+':
                                res.append(l+r)
                            elif c == '-':
                                res.append(l-r)
                            else: # c==*
                                res.append(l*r)
            memo[s] = res
            return res 
        return dfs(expression,memo)