LeetCode 55 Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

In first solution, i try to search every possible path to the end. return true until found one path. but the solution is too slow.


class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if(len(nums) < 2):
            return True

        return self.innerCanJump(nums)

    def innerCanJump(self, nums):

        if(len(nums) == 0):
            return False

        if(len(nums) == 1):
            return True

        for i in range(nums[0]):
            if self.innerCanJump(nums[i+1:]):
                return True

        return False

The most important point in this case is how far we can reach, not in which path, so just mark the longest station we can reach and check weather the end point in this range.

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach = 1
        for i in range(len(nums)):
            if (reach < i + 1):
                break;
            reach = max(reach, i + 1 + nums[i])
        return reach >= len(nums)