Python Greedy & BFS Solution


  • 0

    Greedy Solution(Accepted, 56 ms):

    class Solution(object):
        def canJump(self, nums):
            n=len(nums)-1
            jump=n
            for i in xrange(n-1,-1,-1):
                if i+nums[i]>=n or i+nums[i]>=jump:
                    jump=i # jump is the lowest index that has path(s) to last index
            return jump==0 or i+nums[i]>=n
    

    BFS Solution(Time Limit Exceeded, but idea is right):

    class Solution(object):
        def canJump(self, nums):
            if len(nums)==1:
                return True
            box=[[0,nums[0]]] # box keeps nodes that can be jumped to
            i=0
            while 1:
                if i==len(box):
                    break
                # add left node to box
                left=box[i][0]-box[i][1]
                for e in xrange(max(left,1),i):
                    if [e,nums[e]] not in box:
                        box.append([e,nums[e]])
                # add right node to box
                right=box[i][0]+box[i][1]
                if right>=len(nums)-1: # return True if a node can reach the last index
                    return True
                else:
                    for e in xrange(i+1,right+1):
                        if [e,nums[e]] not in box:
                            box.append([e,nums[e]])
                i+=1
            return False # if no node in the box can reach the last index

Log in to reply
 

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