Simple python DFS (beats 95%)


  • 0
    T
    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            if not stones:
                return False
            stoneToIndex = {s: i for i, s in enumerate(stones)}
            visited = set()
            stack = [(0, 0)]
            while stack:
                k, i = stack.pop()
                if i == len(stones) - 1:
                    return True
                visited.add((k, i))
                for c in (-1, 0, 1):
                    nextK = k + c
                    nextStone = stones[i] + nextK
                    if (nextStone in stoneToIndex and
                        stoneToIndex[nextStone] > i and
                        (nextK, stoneToIndex[nextStone]) not in visited):
                        stack.append((nextK, stoneToIndex[nextStone]))
            return False
    

Log in to reply
 

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