A much faster Python backtracking solution with cache

  • 2

    I did a test for my code, it takes 84ms to finish without cache while it only takes 44ms with it.
    Haven't seen anyone else uses cache to solve this problem yet, I think it's good to share my solution here:)

    def diffWaysToCompute(input):
        def collect(s, cache):
            ops = {'+':lambda x, y:x+y, '-':lambda x, y:x-y, '*':lambda x, y:x*y}
            if not cache.has_key(s):
                ret = []
                for i, c in enumerate(s):
                    if c in '+-*':
                        for p in collect(s[:i], cache):
                            for n in collect(s[i+1:], cache):
                                ret.append(ops[c](p, n))
                if not ret:
                cache[s] = ret
            return cache[s]
        return collect(input, {})

  • 0

    It's not backtracking, but it's definitely a smart solution

  • 0

    this is a smart solution; the cache removes the duplicate computation on the same substring.

Log in to reply

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