# [Python] Documented solution that is easy to understand

• ``````class Solution(object):
def canCross(self, stones):

# create a dictionary where the keys are the stones
# and the values are empty sets that will contain
# integers which represent the jump lengths that
# can reach the stone represented by the key
d = dict((x,set()) for x in stones)

# catches a tricky test case: stones = [0,2]
if stones[1] != 1:
return False

# the problems says that the first jump made is
# always of length 1 and starts at stone 0. That
# means the jump length that was used to reach
# stone 1 is 1 so I add it into the set at stone 1

# iterate over all the stones after 0
for i in xrange(len(stones[1:])):

# iterate over each jump length used to reach
# the current stone
for j in d[stones[i]]:

# iterate over every jump length possible
# (k-1, k, k+1) given the current jump length
for k in xrange(j-1, j+2):

# if that jump length lands on a stone
if k > 0 and stones[i]+k in d:

# add that jump length used to get there to
# the set of jump lengths for the stone the
# jump puts the frog on

# if the last stone has any jump lengths in it's
# set, that means that it is possible to get to
# the last stone
return d[stones[-1]] != set()``````

• Maybe the comments are good, but to be honest the first thing I did was remove them and only read the actual code :-P. I like seeing the whole code at once, and seeing how much it is. The missing syntax highlighting also makes it hard to just focus on the code. (You'd get syntax highlighting if you put the formatting backticks on their own line and also after the code.)

Anyway, I'd do a few things differently, like catching non-starters before I do any other work, and not looping over `stones` by index.

``````def canCross(self, stones):
if stones[1] != 1:
return False
d = {x: set() for x in stones}
for x in stones[:-1]:
for j in d[x]:
for k in xrange(j-1, j+2):
if k > 0 and x+k in d:
return bool(d[stones[-1]])
``````

Could even be `for x in stones:`, that might do a little more work at the end but would prevent creating that almost complete slice of `stones`.

• @StefanPochmann

Thanks for the protip on the back ticks!

TBH I don't know why I didn't put the check on top before I constructed by dict. I am going to leave the order just to avoid confusion.

Also, good call on taking out xrange in favor of

``````for x in stones:
``````

I was doing something differently when I first started and totally forgot that I wasn't leveraging the index anymore.

• @StefanPochmann
Hi Stefan,
I guess I saw you use for num in nums[:-1] more than once here in leetcode.
May I ask you why you didn't use for num in nums?

Thanks

• Hi! Need some help. Inspired by the solution here above, I tried coding it up on my own and I'm running into TLE. Can someone help me identify what's wrong? Thanks

``````from collections import defaultdict

class Solution:
lookup=defaultdict(int)
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
lookup=defaultdict(set)