Iterative python DFS, beats about 90%


  • 0
    I

    This problem basically boils down to "see if there is a path between 2 nodes in a graph":

    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            if not stones or (len(stones) >= 1 and stones[1] != 1):
                return False
                
            visited = set()
            avail_stones = set(stones)
            stack = deque([(1,1)])
            
            while stack:
                curr_stone, curr_jump_dist = stack.pop()
                if curr_stone == stones[-1]:
                    return True
                    
                visited.add((curr_stone, curr_jump_dist))
                for next_jump_dist in (curr_jump_dist-1, curr_jump_dist, curr_jump_dist+1):
                    next_stone = curr_stone + next_jump_dist
                    if next_stone in avail_stones and (next_stone,next_jump_dist) not in visited:
                        stack.append((next_stone, next_jump_dist))
                        
            return False

Log in to reply
 

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