recursive python using indices and memorization, beating 94%


  • 0
    F

    The naive one is similar to other people's posts, but it uses indices instead of many substrings for the sake of reducing O(n) in substring. The following beats 45%.

    class Solution(object):
        def diffWaysToCompute(self, input):
            """
            :type input: str
            :rtype: List[int]
            """
            return self.divideAndConquer(input, 0, len(input))
            
        def divideAndConquer(self, input, start, end):
            if start >= end:
                return []
            res = []
            for i in range(start, end):
                if input[i] in ('+', '-', '*'):
                    left = self.divideAndConquer(input, start, i)
                    right = self.divideAndConquer(input, i + 1, end)
                    for a in left:
                        for b in right:
                            n = a + b if input[i] == '+' else (a - b if input[i] == '-' else a * b)
                            res.append(n)
            return res if res else [int(input[start:end])]
    

    Then the further improved one is using memorization, and it speeds up much more, beating 94%:

    class Solution(object):
        def diffWaysToCompute(self, input):
            """
            :type input: str
            :rtype: List[int]
            """
            return self.divideAndConquer(input, 0, len(input), {})
            
        def divideAndConquer(self, input, start, end, memo):
            if start >= end:
                return []
            if (start, end) in memo:
                return memo[(start, end)]
            res = []
            for i in range(start, end):
                if input[i] in ('+', '-', '*'):
                    left = self.divideAndConquer(input, start, i, memo)
                    right = self.divideAndConquer(input, i + 1, end, memo)
                    for a in left:
                        for b in right:
                            n = a + b if input[i] == '+' else (a - b if input[i] == '-' else a * b)
                            res.append(n)
            memo[(start, end)] = res if res else [int(input[start:end])]
            return memo[(start, end)]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.