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), ands[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 <= 105s[i]is either'0'or'1'.s[0] == '0'1 <= minJump <= maxJump < s.length
Solutions
This code solves a jump game problem where you need to determine if you can reach the last character of a string by jumping only on '0's, with each jump being between minJump and maxJump positions. It first checks if the last character is '0' (required to win); if not, it returns false immediately. Then it uses a difference array optimization to efficiently track reachable positions: as it iterates through the string, it maintains a running sum (total) that represents whether the current position can be reached from any previous position within the valid jump range. When it finds a reachable '0' at position i, it marks the range [i + minJump, i + maxJump] as containing new reachable positions by incrementing and decrementing specific indices in the arr array—this allows the algorithm to update an entire range in O(1) time instead of iterating through each position individually. Finally, it returns whether total > 0 at the end, indicating at least one valid path exists to reach the destination.
/**
* @param {string} s
* @param {number} minJump
* @param {number} maxJump
* @return {boolean}
*/
var canReach = function(s, minJump, maxJump) {
if (s[s.length - 1] !== '0') return false;
const n = s.length;
const arr = Array(n + 1).fill(0);
arr[0] = 1;
arr[1] = -1;
let total = 0;
for (let i = 0; i < n; i++) {
total += arr[i];
if (s[i] === '0' && total > 0 && i + minJump < n) {
arr[i + minJump]++;
arr[Math.min(i + maxJump + 1, n)]--;
}
}
return total > 0;
};