1871-jump-game-vii.js

/**
 * @param {string} s
 * @param {number} minJump
 * @param {number} maxJump
 * @return {boolean}
 */
const canReach = function(s, minJump, maxJump) {
  const n = s.length
  const queue = [0]
  let mx = 0
  const { max, min } = Math
  while(queue.length) {
    const i = queue.shift()
    for(let j = max(i + minJump, mx + 1); j < min(s.length, i + maxJump + 1); j++) {
      if(s[j] === '0') {
        if(j === n - 1) return true
        queue.push(j)
      }
    }
    mx = i + maxJump
  }
  
  return false
};


// another

/**
 * @param {string} s
 * @param {number} minJump
 * @param {number} maxJump
 * @return {boolean}
 */
const canReach = function(s, minJump, maxJump) {
  let n = s.length;
  const {max, min} = Math
  if (s[n - 1] != '0') return false;
  const pre_sum = Array(n + 1).fill(0);
  const check = Array(n + 1).fill(0);
  check[1] = 1;
  pre_sum[1] = 1;
  for (let i = 1; i < n; i++) {
      pre_sum[i + 1] = pre_sum[i];
      if (s[i] == '1') continue;
      if (i < minJump) continue;
      let r = i - minJump;
      let l = max(0, i - maxJump);
      if (pre_sum[r + 1] - pre_sum[l] == 0) continue;
      check[i + 1] = true;
      pre_sum[i + 1]++;
  }
  return check[n];
};

// another

/**
 * @param {string} s
 * @param {number} minJump
 * @param {number} maxJump
 * @return {boolean}
 */
const canReach = function(s, minJump, maxJump) {
  const n = s.length, dp = Array(n).fill(0)
  dp[0] = 1
  let pre = 0
  for(let i = 1; i < n; i++) {
    if(i >= minJump) {
      pre += dp[i - minJump]
    }
    if(i > maxJump) pre -= dp[i - maxJump - 1]
    dp[i] = pre > 0 && s[i] === '0' ? 1 : 0
  }
  return dp[n - 1]
};

// another

/**
 * @param {string} s
 * @param {number} minJump
 * @param {number} maxJump
 * @return {boolean}
 */
const canReach = function(s, minJump, maxJump) {
  const n = s.length
  const dp = Array(n).fill(0)
  dp[0] = 1
  let pre = 0
  for(let i = 1; i < n; i++) {
    if(i < minJump) continue
    if(i >= minJump) pre += dp[i - minJump]
    if(i > maxJump) pre -= dp[i - maxJump - 1]
    dp[i] = pre > 0 && s[i] === '0' ? 1 : 0
  }
  
  return dp[n - 1] ? true : false
};