10 lines in Python


  • 0
    class Solution(object):
        def canCross(self, stones):
            memo, stones, last = {}, set(stones), stones[-1]
            def helper(pos, jump):
                if pos == last:                      return True
                if jump <= 0 or pos not in stones:   return False
                if (pos, jump) in memo:              return memo[pos, jump]
                for nex in {jump, jump - 1, jump + 1}:
                    if helper(pos + nex, nex): return True
                memo[pos, jump] = False
                return False
            return helper(1, 1)
    
    # 39 / 39 test cases passed.
    # Status: Accepted
    # Runtime: 166 ms
    

    Let's talk about complexity. Right off the bat, we can get an easy big-O estimation by considering that we do 3 sub-recursive call at each recursive call, leading to an O(3^n) complexity. However, we can achieve a better time complexity estimation by observing that for each position pos, there are maximum pos-1 possible jumps that can lead to position pos. Therefore, we have a recursive tree with at most 1 + 2 + ... + n nodes, leading to a complexity of O(n^2). Space is also O(n^2) since we need to store in memo the results of the negative calls.

    Even shorter BFS (iterative):

    class Solution(object):
        def canCross(self, stones):
            visits, stones, last, queue = {(1, 1)}, set(stones), stones[-1], [(1, 1)]
            for pos, jump in queue:
                if pos == last: return True
                if jump <= 0 or pos not in stones: continue
                for nex in {jump, jump - 1, jump + 1}:
                    if (pos + nex, nex) not in visits:
                        visits.add((pos + nex, nex))
                        queue.append((pos + nex, nex))
            return False
    

Log in to reply
 

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