Simple Python DFS solution with memoization


  • 0
    K

    DFS implementation with only 3 step sizes allowed. range(max(step-1, 1), step+2) is used to just avoid step size 0 for the initial case.

    class Solution(object):
        def canCross(self, stones):
            s, end, d = set(stones), stones[-1], {}
            return self.helper(0, 1, s, end, d)
    
        def helper(self, curr, step, s, end, d):
            if (curr, step) in d:
                return False
            elif curr+step == end:
                return True
            elif curr+step not in s:
                return False
            
            for i in range(max(step-1, 1), step+2):
                if self.helper(curr+step, i, s, end, d):
                    return True
            
            d[(curr, step)] = False
            return False
    

Log in to reply
 

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