Python, simple recursive w/memoization, 95%


  • 0
    A
    class Solution(object):
        def canCross_h(self, stones, current, target, step):
            if (current,step) in self.memo : return self.memo[(current,step)]
            if current == target : return True
            if current > target : return False
            ord = False
            if current+step+1 in stones:
                ord = ord or self.canCross_h(stones, current+step+1, target, step+1)
            if step > 0 and current+step in stones:
                ord = ord or self.canCross_h(stones, current+step, target, step)
            if step > 1 and current+step-1 in stones:
                ord = ord or self.canCross_h(stones, current+step-1, target, step-1)
            self.memo[(current,step)] = ord
            return ord
            
        def canCross(self, stones):
            self.memo = {}
            return self.canCross_h(set(stones),stones[0],stones[-1],0)
    

Log in to reply
 

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