A much faster Python backtracking solution with cache


  • 2
    C

    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:
                    ret.append(int(s))
                
                cache[s] = ret
                
            return cache[s]
            
        return collect(input, {})

  • 0
    F

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


  • 0
    S

    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.