Jump Game VII

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

Approaches

Checkout 3 different approaches to solve Jump Game VII. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming

This approach uses dynamic programming to solve the problem. We define an array dp where dp[i] is true if index i is reachable from index 0, and false otherwise. To determine dp[i], we check if s[i] is '0' and if there exists any previously reachable index j that can jump to i. A jump from j to i is valid if i - maxJump <= j <= i - minJump. This involves a nested loop, where the outer loop iterates through each index i and the inner loop checks the valid window of previous indices j.

Algorithm

Create a boolean array dp of size n, where dp[i] will be true if index i is reachable, and false otherwise.
Initialize dp[0] to true since we start at index 0.
Iterate through the string from i = 1 to n-1.
For each index i, if s[i] is '0', iterate through all possible previous indices j from which a jump to i is valid.
The valid range for a previous index j is i - maxJump <= j <= i - minJump.
If we find any j in this range for which dp[j] is true, it means we can reach i. We set dp[i] = true and can break the inner loop for the current i.
After iterating through all i, the value of dp[n-1] will tell us if the last index is reachable.

In this approach, we build a boolean array dp of the same size as the input string s. dp[i] stores whether index i is reachable. We know dp[0] is true because we start there. For every other index i from 1 to n-1, we can determine its reachability based on the reachability of previous indices.

An index i is reachable if two conditions are met:

The character at that index, s[i], must be '0'.
There must be at least one reachable index j from which we can jump to i. The jump condition j + minJump <= i <= j + maxJump can be rearranged to find the range of j for a given i: i - maxJump <= j <= i - minJump.

So, for each i, we check if s[i] is '0'. If it is, we then scan the dp array in the range [max(0, i - maxJump), i - minJump] to see if any dp[j] is true. If we find one, we set dp[i] to true and move to the next index. The final answer is the value of dp[s.length - 1].

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        if (s.charAt(n - 1) == '1') {
            return false;
        }

        boolean[] dp = new boolean[n];
        dp[0] = true;

        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '0') {
                for (int j = Math.max(0, i - maxJump); j <= i - minJump; j++) {
                    if (dp[j]) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }

        return dp[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n * k), where n is the length of the string and k is `maxJump - minJump`. For each index `i`, we might scan up to `k` previous indices. In the worst case, `k` can be close to `n`, leading to an `O(n^2)` complexity.Space Complexity: O(n), where n is the length of the string `s`. This is for the `dp` array used to store the reachability of each index.

Pros and Cons

Pros:

It's a direct translation of the problem's recurrence relation, making it relatively easy to understand and implement.

Cons:

The nested loop structure leads to a high time complexity, which will result in a 'Time Limit Exceeded' error on larger inputs.

Code Solutions

Checking out 4 solutions in different languages for Jump Game VII. Click on different languages to view the code.

class Solution { public boolean canReach ( String s , int minJump , int maxJump ) { int n = s . length (); int [] pre = new int [ n + 1 ]; pre [ 1 ] = 1 ; boolean [] f = new boolean [ n ]; f [ 0 ] = true ; for ( int i = 1 ; i < n ; ++ i ) { if ( s . charAt ( i ) == '0' ) { int l = Math . max ( 0 , i - maxJump ); int r = i - minJump ; f [ i ] = l <= r && pre [ r + 1 ] - pre [ l ] > 0 ; } pre [ i + 1 ] = pre [ i ] + ( f [ i ] ? 1 : 0 ); } return f [ n - 1 ]; } }

Video Solution

Watch the video walkthrough for Jump Game VII

Patterns:

Sliding WindowDynamic ProgrammingPrefix Sum

Data Structures:

String