1871. Jump Game VII

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

 

Solutions

Solution: Dynamic Programming

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

 

JavaScript

/**
 * @param {string} s
 * @param {number} minJump
 * @param {number} maxJump
 * @return {boolean}
 */
const canReach = function (s, minJump, maxJump) {
  const size = s.length;

  if (s[size - 1] !== '0') return false;
  const dp = new Array(size).fill(0);
  let count = 0;

  dp[minJump] += 1;
  dp[maxJump + 1] -= 1;

  for (let index = 1; index < size; index++) {
    const value = s[index];

    count += dp[index];
    if (count <= 0 || value === '1') continue;
    if (index + minJump < size) dp[index + minJump] += 1;
    if (index + maxJump + 1 < size) dp[index + maxJump + 1] -= 1;
  }
  return count > 0;
};