You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:
i + minJump <= j <= min(i + maxJump, s.length - 1), ands[j] == '0'.Return true if you can reach index s.length - 1 in s, or false otherwise.
Example 1:
Input: s = "011010", minJump = 2, maxJump = 3 Output: true Explanation: In the first step, move from index 0 to index 3. In the second step, move from index 3 to index 5.
Example 2:
Input: s = "01101110", minJump = 2, maxJump = 3 Output: false
Constraints:
2 <= s.length <= 10^5s[i] is either '0' or '1'.s[0] == '0'1 <= minJump <= maxJump < s.length
The description was taken from https://leetcode.com/problems/jump-game-vii/.
#O(N) Time, O(N) Spaceclass Solution: def canReach(self, s: str, minJump: int, maxJump: int) -> bool: def bfs() -> bool: queue, last_leap = collections.deque([0]), 0 while queue: i = queue.popleft() left = max(i + minJump, last_leap) for right in range(left, min(i + maxJump + 1, len(s))): if s[right] == "0": queue.append(right) if right == len(s)-1: return True last_leap = i + maxJump return False return bfs()What makes this question more difficult than many of the previous Jump Game questions, is the requirement that we can't go past the last element of the array. Not only that, but we can only make jumps in increments between the minimum and maximum jumps given, inclusively. That means that if we were standing on a zero one element away from the end of the array, and we had the minimum jump of two, we wouldn't be able to make that jump because we would overshoot the target.
What we can do is another greedy, Breadth-First Search type solution, similar to the previous ones.
What we will do is collect every index with a zero and put them into a queue. During each iteration, we will see if the position can get us farther than where we are at, or if we are already past it. If it can get us farther than we are at, it will be our starting position for our search of zeros to collect, and the ending position will be the max jump or the end of the array depending on where we are at in our traversal.
Let's start by creating our bfs function.
def bfs() -> bool:
We'll initialize our queue with the first index, and the last leap we took as zero since we haven't taken a leap yet.
This last leap variable is a sort of anchor or bookmark that we will throw as far as we can at the end of each iteration so that we can keep it moving to the right and knowing where we left off the last time around.
queue, last_leap = collections.deque([0]), 0
While we have items in our queue, we have zeros that we can jump from, which means we still have chances to reach the end of the array.
while queue:
At the beginning of each index, we will pop a zero index off the queue.
We will compare that index plus the minimum jump we can make, to the last leap we took. If the last leap we took was farther than the minimum jump we could take from here, then we would be moving to the left of the last leap in order to utilize this zero jump pad.
If that is the case, we will just use our last leap as the left bound for the search.
left = max(i + minJump, last_leap)
Now that we have a left bound for the search of the current window, we will set our right bound to either the max jump we can take or the last index of the array so that we don't overshoot our target, remember we have to land on the last index and not past it.
for right in range(left, min(i + maxJump + 1, len(s))):
Within the left and right bounds of each window, we will try to collect each zero we can find and throw them into our queue.
if s[right] == "0": queue.append(right)
If we have landed on the last index of the array, we have successfully made it so we will return true.
if right == len(s)-1: return True
Otherwise, we will make the last leap from this window to the farthest we can possibly jump and continue collecting zeros.
last_leap = i + maxJump
With this last leap, we are able to get either a range of a max jump to another max jump, or we can get a min jump to a max jump if the min jump position is greater than the previous max jump we took. This allows us to be more flexible with our window options and to keep pushing our left bound as far as it can go.
If we emptied out our queue and never got to the last index of the array, then we exhausted all of our options. If that is the case, we will return false because we had no option to get there.
return False
We will finish by returning the results of this BFS, which would tell us if we were able to reach the last index or not.
return bfs()
This solution allows us to search different groups, similar to other jump game problems.
If we have the test case "011010001010", where the min jump is two and the max jump is three, we would split the left bound of our searches, into groups like this.
"011010001010"
We would then have the search space from each colored spot to the distance of the max jump, one place to the left in this example, to look for zeros to collect. That is what makes this question and other questions like this so confusing. We'd think that we can't land on ones because that is what the question description states, but we need to traverse every index of the array.
Each index we pop off the queue is a zero, so that means we are always at a valid jumping spot. What we can visualize us doing is standing on the jumping spots, but looking forward to the range of our jump budget for any zeros we can pluck.