Different Ways to Add Parentheses LeetCode solution in Python

1
# Runtime: 49 ms (Top 17.3%) | Memory: 13.54 MB (Top 39.1%)
2

3

4
class Solution(object):
5
    def diffWaysToCompute(self, input):
6
        m = {}
7
        return self.dfs(input, m)
8

9
    def dfs(self, input, m):
10
        if input in m:
11
            return m[input]
12
        if input.isdigit():
13
            m[input] = int(input)
14
            return [int(input)]
15
        ret = []
16
        for i, c in enumerate(input):
17
            if c in "+-*":
18
                l = self.diffWaysToCompute(input[:i])
19
                r = self.diffWaysToCompute(input[i + 1 :])
20
                ret.extend(eval(str(x) + c + str(y)) for x in l for y in r)
21
        m[input] = ret
22
        return ret