I test it on my local and seems works fine.
class Solution: # @param A, a list of integers # @return a boolean def canJump(self, A): pos = 0 if A == 0 and len(A) != 1: return False if A[pos] >= len(A) - 1: return True return any(self.canJump(A[x:]) for x in range(1,A[pos]))
AFAIK, python pass reference by default. But in this case of
A[x:], they will do a deep copy, which means it will consume a pile of memory in the entire recursion.
I did some change like below. At least, it isn't MLE any more.
class Solution: # @param A, a list of integers # @return a boolean def canJumpIntern(self, A, pos): if A[pos] >= len(A) - 1: return True return any(self.canJumpIntern(A, x) for x in range(1,A[pos])) def canJump(self, A): pos = 0 if A == 0 and len(A) != 1: return False return self.canJumpIntern(A, 0)
Maybe I am wrong, I don't quite understand what exactly the strategy in your code. For example,
A[pos] stands for length. So,
x is also a length. How to understand it becomes a index
I suggest to elaborate the idea.
Hello Shangrilla, thank you for the respond.
My strategy is using recursive. So if we can reach A[pos], then the function result depends on the result of the rest array A[pos:].
A[pos] is a length, you're right, and it is the maximum steps we can go. So I'm iterate on all possible steps to see if there's a way to reach the end.
Not sure I explained it clear, let me know if you have any question.
By the way your solution didn't work for me, the test case [2,3,0,1,4] will get into infinite loop and fail with "maximum recursion depth exceeded" error.
I hit a dead end by keeping your recursive idea. In essence, I don't think it can be solved by this way. I suggest to find a good approach from this post
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.