Jump Game VII

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), and
• s[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.
Constraints:

• 2 <= s.length <= 105
• s[i] is either '0' or '1'.
• s[0] == '0'
• 1 <= minJump <= maxJump < s.length

Solution:

So what we have to do here is, start from the first index, which has to be 0, otherwise return False. If it’s 0, then we have to move forward if and only if the two conditions are satisfied:

• i + minJump <= j <= min(i + maxJump, s.length - 1)
• s[j] == '0'

First condition gives us the range to check and second one gives us the filtering condition. We can use BFS here to explore all valid cases but that will give TLE. So we can skip the already done calculations.

The code here is:

def jump(s, minJump, maxJump):
        if s[-1] != "0":
            return False
        q = deque([0])
        max_reached = 0
        while q:
            curr = q.popleft()
            if curr == len(s)-1:
                return True
            start = max(curr+minJump, max_reached)
            for i in range(start, min(curr+maxJump+1, len(s))):
                if s[i] == '0':
                    q.append(i)
            max_reached = curr+maxJump
        return False

So in this function jump, we start by checking if first value is 0 or not as required by the question. Then we create a queue with 0 as its first value. We also maintain a max_reached variable to skip the already done calculations. while q, do: we pop the queue, check if value is the answer or not. If not then we proceed. Start is created, which is max of curr+minJump or max_reached. This max function helps us skip the extra calculations. How?

By checking for max, we set the farthest point till where we have checked and added the indexes to queue, as the start. Think for a min here. If we have already checked till index 7 last time and max_reached=7. Now for next iteration, if curr+minJump says any number less than max_reached, that means loop will run max_reached-curr+minJump times extra. We can skip that by just getting the max value.

Run the for loop from start to min(curr+maxJump+1, len(s)) as said by the question. If it is a valid index that is if s[i] == “0”, append i to queue.

Update the max_reached to curr_max_Jump. Then continue. If curr == len(s) — 1, return True. After the loop, it returns False, that means none of the possible values in the queue was our answer.

That’s all. Thanks.