Use hash to save time

  • 0

    Divide and conquer is the basic idea to solve this problem. However, we can use hash to save computing time since some parts of the input could be reused without recalculating them. It can save up to 50% of computing time according to my statistical measurement.

    Here is the code.

    class Solution(object):
        def diffWaysToCompute(self, input):
            :type input: str
            :rtype: List[int]
            # hashed dict to save partial result
            res = {}
            return self.diffWaysToCompute2(input, res)
        def diffWaysToCompute2(self, input, res):
                # if the input has been calculated before, just pull it.
                return res[input]
                # divide and conquer for the uncalculated input
                if input.isdigit():
                    res[input] = [int(input)]
                    res2 = []
                    res[input] = res2
                    # you can use list comprehension here but it is too specific for python;
                    for ind,i in enumerate(input):
                        if i in '+-*':
                            for j1 in self.diffWaysToCompute2(input[:ind], res):
                                for j2 in self.diffWaysToCompute2(input[ind+1:], res):
                                    res2.append(self.helper(j1, j2, input[ind]))
            return res[input]
        # helper function; avoid using eval and str functions since they are time-consuming.
        def helper(self, m, n, op):
            if op == '+':
                return m+n
            elif op == '-':
                return m-n
            elif op == '*':
                return m*n

    Thanks for reading!

Log in to reply

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