[Python] Documented solution that is easy to understand


  • 2
    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 
                    # (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
                            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()

  • 5

    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}
        d[1].add(1)
        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:
                        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 of stones.


  • 0

    @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.


Log in to reply
 

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