1871. Jump Game VII LeetCode Solution

In this guide, you will get 1871. Jump Game VII LeetCode Solution with the best time and space complexity. The solution to Jump Game VII problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Jump Game VII solution in C++
  4. Jump Game VII solution in Java
  5. Jump Game VII solution in Python
  6. Additional Resources
1871. Jump Game VII LeetCode Solution image

Problem Statement of 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.

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

1871. Jump Game VII LeetCode Solution in C++

class Solution {
 public:
  bool canReach(string s, int minJump, int maxJump) {
    int count = 0;
    vector<bool> dp(s.length());
    dp[0] = true;

    for (int i = minJump; i < s.length(); ++i) {
      count += dp[i - minJump];
      if (i - maxJump > 0)
        count -= dp[i - maxJump - 1];
      dp[i] = count && s[i] == '0';
    }

    return dp.back();
  }
};
/* code provided by PROGIEZ */

1871. Jump Game VII LeetCode Solution in Java

class Solution {
  public boolean canReach(String s, int minJump, int maxJump) {
    int count = 0;
    boolean dp[] = new boolean[s.length()];
    dp[0] = true;

    for (int i = minJump; i < s.length(); ++i) {
      count += dp[i - minJump] ? 1 : 0;
      if (i - maxJump > 0)
        count -= dp[i - maxJump - 1] ? 1 : 0;
      dp[i] = count > 0 && s.charAt(i) == '0';
    }

    return dp[dp.length - 1];
  }
}
// code provided by PROGIEZ

1871. Jump Game VII LeetCode Solution in Python

class Solution:
  def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
    count = 0
    dp = [True] + [False] * (len(s) - 1)

    for i in range(minJump, len(s)):
      count += dp[i - minJump]
      if i - maxJump > 0:
        count -= dp[i - maxJump - 1]
      dp[i] = count and s[i] == '0'

    return dp[-1]
# code by PROGIEZ

Additional Resources

See also  695. Max Area of Island LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.