1871

(Medium)

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

Companies: Google, Amazon

Related Topics:
Two Pointers, String, Prefix Sum

Similar Questions:

• Jump Game II (Medium)
• Jump Game (Medium)
• Jump Game III (Medium)
• Jump Game IV (Hard)
• Jump Game V (Hard)
• Jump Game VI (Medium)
• Jump Game VII (Medium)
• Jump Game VIII (Medium)
• Count Vowel Strings in Ranges (Medium)
• Maximum Number of Jumps to Reach the Last Index (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/jump-game-vii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(maxJump - minJump)
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        if (s.back() == '1') return false;
        queue<int> q;
        int j = 0, prev = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (i - prev > maxJump) return false;
            if (s[i] == '1') continue;
            j = max(j, i - maxJump);
            while (i - j >= minJump) {
                if (s[j] == '0') q.push(j);
                ++j;
            }
            while (q.size() && i - q.front() > maxJump) q.pop();
            if (q.empty()) s[i] = '1'; // mark this position as non-reachable.
            else prev = i;
        }
        return q.size();
    }
};

Solution 2. Two Pointers

Mark reacheable position using '2'. For each s[i] == '2', we traverse i + minJump <= j <= i + maxJump and turn s[j] to 2 if s[j] == '0'.

Pointer j can be monotonically increasing so that both pointer i and j at most traverse the array once.

// OJ: https://leetcode.com/problems/jump-game-vii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        if (s.back() == '1') return false;
        s[0] = '2'; // mark s[0] as reacheable
        int j = 0;
        for (int i = 0; i < s.size() && s.back() != '2'; ++i) {
            if (s[i] != '2') continue; // only extend reacheable points
            j = max(j, i + minJump); // `j` is at least `i + minJump`
            while (j < s.size() && j - i <= maxJump) { // try to extend until `j > i + maxJump`
                if (s[j] == '0') s[j] = '2'; // mark `s[j]` as reacheable if `s[j] == '0'`
                ++j;
            }
        }
        return s.back() == '2';
    }
};

Solution 3. DP + Sliding Window

dp[i] = true if we can reach s[i].

active is the number of previous positions that we can jump from.

For each i, the [i - maxJump, i + minJump] forms a sliding window, and we only update the active when '0' goes in/out of the window.

// OJ: https://leetcode.com/problems/jump-game-vii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/jump-game-vii/discuss/1224804/JavaC%2B%2BPython-One-Pass-DP
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        if (s.back() == '1') return false;
        int N = s.size(), active = 0;
        vector<int> dp(N);
        dp[0] = true;
        for (int i = 1; i < N; ++i) {
            if (i - minJump >= 0 && dp[i - minJump]) ++active;
            if (i - maxJump - 1 >= 0 && dp[i - maxJump - 1]) --active;
            dp[i] = s[i] == '0' && active;
        }
        return dp.back();
    }
};

Or

// OJ: https://leetcode.com/problems/jump-game-vii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        if (s.back() == '1') return false;
        int N = s.size(), active = 0;
        s[0] = '2';
        for (int i = 1; i < N && s.back() != '2'; ++i) {
            if (i - minJump >= 0 && s[i - minJump] == '2') ++active;
            if (i - maxJump - 1 >= 0 && s[i - maxJump - 1] == '2') --active;
            if (s[i] == '0' && active) s[i] = '2';
        }
        return s.back() == '2';
    }
};