# 10 lines in Python

• ``````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: