Jump Game VII
Problem
String s of '0'/'1'. From index i you can jump to j in [i+minJump, i+maxJump] iff s[j]='0'. Return whether you can reach index n−1 from 0.
s = "011010", minJump = 2, maxJump = 3truedef can_reach(s, minJump, maxJump):
n = len(s)
if s[-1] != '0': return False
dp = [False] * n
dp[0] = True
pre = 0 # count of reachable positions in window
for i in range(1, n):
if i >= minJump: pre += int(dp[i - minJump])
if i > maxJump: pre -= int(dp[i - maxJump - 1])
dp[i] = (s[i] == '0' and pre > 0)
return dp[-1]function canReach(s, minJump, maxJump) {
const n = s.length;
if (s[n - 1] !== '0') return false;
const dp = new Array(n).fill(false);
dp[0] = true;
let pre = 0;
for (let i = 1; i < n; i++) {
if (i >= minJump) pre += dp[i - minJump] ? 1 : 0;
if (i > maxJump) pre -= dp[i - maxJump - 1] ? 1 : 0;
dp[i] = (s[i] === '0' && pre > 0);
}
return dp[n - 1];
}class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
if (s.charAt(n - 1) != '0') return false;
boolean[] dp = new boolean[n];
dp[0] = true;
int pre = 0;
for (int i = 1; i < n; i++) {
if (i >= minJump) pre += dp[i - minJump] ? 1 : 0;
if (i > maxJump) pre -= dp[i - maxJump - 1] ? 1 : 0;
dp[i] = s.charAt(i) == '0' && pre > 0;
}
return dp[n - 1];
}
}bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
if (s.back() != '0') return false;
vector<bool> dp(n, false);
dp[0] = true;
int pre = 0;
for (int i = 1; i < n; i++) {
if (i >= minJump) pre += dp[i - minJump] ? 1 : 0;
if (i > maxJump) pre -= dp[i - maxJump - 1] ? 1 : 0;
dp[i] = s[i] == '0' && pre > 0;
}
return dp[n - 1];
}Explanation
From index i you can jump to any j in the window [i+minJump, i+maxJump], but only if s[j] = '0'. The naive check would scan that whole window for each index; the speed-up is a sliding window count.
dp[i] is true when index i is reachable. Looking backwards, i is reachable if any reachable index sits in [i-maxJump, i-minJump]. Instead of re-scanning that range, we keep a running counter pre of how many reachable indices are currently inside it.
As i advances by one, the window slides: when i >= minJump we add dp[i-minJump] entering on the right, and when i > maxJump we subtract dp[i-maxJump-1] leaving on the left. Then dp[i] is true exactly when s[i] = '0' and pre > 0.
Example: s = "011010", minJump = 2, maxJump = 3. The path 0 → 3 → 5 stays on '0's within the allowed jump range, so the last index is reachable and the answer is true.
Because the window count updates in O(1) per step, the whole scan is O(n).