Very simple python solution to understand


  • 0
    P

    class Solution(object):
    def canCross(self, stones):
    """
    :type stones: List[int]
    :rtype: bool
    """
    d=dict()
    n=len(stones)
    if stones[1]!=1:
    return False
    for i in range(0,n):
    d[stones[i]]=set()

        d[0].add(0)
        d[1].add(1)
        
        i=1
        while i<n:
            s=stones[i]
            
            while(len(d[s])>0):
                
                t=d[s].pop()
                
                if s+t in d and t>0:
                    d[s+t].add(t)
                if s+t-1 in d and t-1>0:
                    d[s+t-1].add(t-1)
                if s+t+1 in d and t+1>0:
                    d[s+t+1].add(t+1)
                
                if s+t==stones[n-1] or s+t-1==stones[n-1] or s+t+1==stones[n-1]:
                    return True
            i+=1
        return False

Log in to reply
 

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