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
d[1].add(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
# (k1, k, k+1) given the current jump length
for k in xrange(j1, 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
d[stones[i]+k].add(k)
# 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()
[Python] Documented solution that is easy to understand


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 nonstarters 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} d[1].add(1) for x in stones[:1]: for j in d[x]: for k in xrange(j1, j+2): if k > 0 and x+k in d: d[x+k].add(k) 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 ofstones
.

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.