# Python DFS easy understanding using memo

• Following is my backtracking solution using dict for memorization.

The memo dict is using for save those dead end. So when we get to the same stone with the same speed we don't need to search further.

``````class Solution(object):
def canCross(self, stones):
self.memo = set()
target = stones[-1]
stones = set(stones)

res = self.bt(stones, 1, 1, target)
return res

def bt(self, stones, cur, speed, target):
# check memo
if (cur, speed) in self.memo:
return False

if cur==target:
return True

if cur>target or cur<0 or speed<=0 or cur not in stones:
return False
# dfs
candidate = [speed-1, speed, speed+1]
for c in candidate:
if (cur + c) in stones:
if self.bt(stones, cur+c, c, target):
return True

return False
``````

• Like this solution. It is also slightly faster than the other python solution: https://discuss.leetcode.com/topic/59570/python-documented-solution-that-is-easy-to-understand

• Good solution. Upvoted! I cleaned up the code by removing some redundant condition checking, e.g., `if cur>target or cur<0` and `if (cur+c) in stones`.

``````class Solution(object):
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
target, stones, memo = stones[-1], set(stones), set()
return self.backtrack(stones, 1, 1, target, memo)

def backtrack(self, stones, pos, jump, target, memo):
if (pos, jump) in memo:
return False
if pos == target:
return True
if jump <= 0 or pos not in stones:
return False
for j in (jump-1, jump, jump+1):
if self.backtrack(stones, pos+j, j, target, memo):
return True
return False
``````

• ``````class Solution(object):
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
stone_set, fail = set(stones), set()
stack = [(0, 0)]
while stack:
stone, jump = stack.pop()
for j in (jump-1, jump, jump+1):
s = stone + j
if j > 0 and s in stone_set and (s, j) not in fail:
if s == stones[-1]:
return True
stack.append((s, j))