Formatted question description: https://leetcode.ca/all/1871.html

1871. Jump Game VII

Level

Medium

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:

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^5
  • s[i] is either '0' or '1'.
  • s[0] == '0'
  • 1 <= minJump <= maxJump < s.length

Solution

Use a list to store the indices that have characters ‘0’ in s. Then use two pointers curr and next to mark the indices that can be reached. Initially, index 0 can be reached and curr = 0. For each curr, find the range of next such that curr + minJump <= next <= curr + maxJump and next < s.length(). Since both curr and next can only move forward, the two pointers can only loop over all indices once. Finally, return true if and only if the index s.length() - 1 can be reached.

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        List<Integer> indices = new ArrayList<Integer>();
        int length = s.length();
        if (s.charAt(length - 1) != '0')
            return false;
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) == '0')
                indices.add(i);
        }
        int size = indices.size();
        boolean[] visited = new boolean[size];
        visited[0] = true;
        int curr = 0, next = 0;
        while (curr < size) {
            while (curr < size && !visited[curr])
                curr++;
            if (curr == size)
                return false;
            int currIndex = indices.get(curr);
            while (next < size && indices.get(next) - currIndex < minJump)
                next++;
            while (next < size && indices.get(next) - currIndex <= maxJump) {
                visited[next] = true;
                next++;
            }
            curr++;
        }
        return visited[size - 1];
    }
}

All Problems

All Solutions