# Python DFS 45 ms beat 100.00% so far

• Very straight forward DFS. The only trick is that k3>k2>k1, so we should check k3 first.

"You are here!
Your runtime beats 100.00 % of python submissions."

39 / 39 test cases passed.
Status: Accepted
Runtime: 45 ms
Submitted: 0 minutes ago

``````def dfs(mapp,jump,current,maximum):
if maximum==current:
return True
k1=current+jump-1
k2=current+jump
k3=current+jump+1
if str(k3) in mapp:
if dfs(mapp,jump+1,k3,maximum):
return True
if jump>0 and str(k2) in mapp:
if dfs(mapp,jump,k2,maximum):
return True
if jump>0 and str(k1) in mapp:
if dfs(mapp,jump-1,k1,maximum):
return True

return False

class Solution(object):
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
mapp={}
maximum=0
for i in range(1,len(stones)):
if stones[i]>2*stones[i-1]+1:
return False
for i in range(0,len(stones)):
mapp[str(stones[i])]=1

return dfs(mapp,0,0,stones[-1])
``````

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