Python Easy Solution

  • 0
    class Solution(object):
        def canCross(self, stones):
            :type stones: List[int]
            :rtype: bool
            n = len(stones)
            if n < 2 or stones[1] != 1: return False
            fails = set() # (pos, last jump)
            diff = [stones[i] - stones[i-1] for i in range(1, n)]
            def query(i, k): # k: last jump
                if i >= n-1: return True
                if (i, k) in fails: return False
                nexts = []
                jump = diff[i]
                j = i
                while j < n and jump <= k+1:
                    if jump in [k-1, k, k+1]: nexts += [(j+1, jump)]
                    j += 1
                    if j < n-1: jump += diff[j]
                r = any(query(*x) for x in nexts)
                if not r: 
                    fails.add((i, k))
                    return False
                return True
            return query(1, 1)

Log in to reply

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