Recursive and Non-recursive solution in Python, faster than 100% python solutions


  • 0
    H

    At first I came up with this recursive solution, it is not difficult to think

    if len(nums) == 1: return True
    for i in reversed(range(len(nums)-1)):
           if i + nums[i] >= len(nums) - 1:
               return self.canJump(nums[0:i+1])
    return False
    

    It is like every time you look from the tail to see whether current index can get you into the last index and if we can reach last index from the current index, then current index becomes a new last index, we do the check again.

    Then I think it is not difficult to come up with the Non-recursive version evolved from the above solution:

            last_index = len(nums) - 1
            for i in reversed(range(last_index)):
                if i + nums[i] >= last_index:
                    last_index = i
            return last_index == 0
    

Log in to reply
 

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