Problem description:

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:

1
2
3
4
5
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:

1
2
Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

Constraints:

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

Solution:

Initial thought: brute force and do exactly what the problem says:

  1. Create a queue of reachable indices starting with 0
  2. While the queue is not empty, pull from front of queue, call this i
  3. Let x go from i + minJumps to i + maxJumps, if s== ‘0’, add to queue
  4. Repeat till queue is empty or reached end
  5. If reached end return true, if queue empty, return false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        q = deque([0])
        max_reach = 0
        
        while q:
            cur_idx = q.popleft()
            if cur_idx == len(s)-1:
                return True
            start = max(cur_idx + minJump, max_reach)
            for i in range(start, min(cur_idx+ maxJump+1, len(s))):
                if s[i] == '0':
                    q.append(i)
            max_reach = cur_idx + maxJump
        return False

time complexity: $O(n)$
space complexity: $O(n)$
reference:
related problem: