Compact python solution

  • 0
    def canCross(self, stones):
        if stones[1]!=1:
            return False
        mp = collections.defaultdict(int)
        for i, s in enumerate(stones):
            mp[s] = i
        check = set()
        def search(pos, prev):
            if (pos,prev) in check: return False
            if pos == len(stones)-1: return True
            for d in [-1, 0, 1]:
                if prev+d <= 0: continue
                loc = stones[pos]+prev+d
                if loc in mp and search(mp[loc], prev+d):
                    return True
            check.add((pos, prev))
            return False
        return search(1, 1)

Log in to reply

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