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
Solution 1: Prefix Sum + Dynamic Programming
We define a prefix sum array pre of length n+1, where pre[i] represents the number of reachable positions in the first i positions of s. We define a boolean array f of length n, where f[i] indicates whether s[i] is reachable. Initially, pre[1] = 1 and f[0] = true.
Consider i ∈ [1, n), if s[i] = 0, then we need to determine whether there exists a position j in the first i positions of s, such that j is reachable and the distance from j to i is within [minJump, maxJump]. If such a position j exists, then we have f[i] = true, otherwise f[i] = false. When determining whether j exists, we can use the prefix sum array pre to determine whether such a position j exists in O(1) time.
The final answer is f[n-1].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
PythonJavaC++GoTypeScriptJavaScript
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
pre = [0] * (n + 1)
pre[1] = 1
f = [True] + [False] * (n - 1)
for i in range(1, n):
if s[i] == "0":
l, r = max(0, i - maxJump), i - minJump
f[i] = l <= r and pre[r + 1] - pre[l] > 0
pre[i + 1] = pre[i] + f[i]
return f[-1](code-box)
class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
int[] pre = new int[n + 1];
pre[1] = 1;
boolean[] f = new boolean[n];
f[0] = true;
for (int i = 1; i < n; ++i) {
if (s.charAt(i) == '0') {
int l = Math.max(0, i - maxJump);
int r = i - minJump;
f[i] = l <= r && pre[r + 1] - pre[l] > 0;
}
pre[i + 1] = pre[i] + (f[i] ? 1 : 0);
}
return f[n - 1];
}
}(code-box)
class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
int pre[n + 1];
memset(pre, 0, sizeof(pre));
pre[1] = 1;
bool f[n];
memset(f, 0, sizeof(f));
f[0] = true;
for (int i = 1; i < n; ++i) {
if (s[i] == '0') {
int l = max(0, i - maxJump);
int r = i - minJump;
f[i] = l <= r && pre[r + 1] - pre[l];
}
pre[i + 1] = pre[i] + f[i];
}
return f[n - 1];
}
};(code-box)
func canReach(s string, minJump int, maxJump int) bool {
n := len(s)
pre := make([]int, n+1)
pre[1] = 1
f := make([]bool, n)
f[0] = true
for i := 1; i < n; i++ {
if s[i] == '0' {
l, r := max(0, i-maxJump), i-minJump
f[i] = l <= r && pre[r+1]-pre[l] > 0
}
pre[i+1] = pre[i]
if f[i] {
pre[i+1]++
}
}
return f[n-1]
}(code-box)
function canReach(s: string, minJump: number, maxJump: number): boolean {
const n = s.length;
const pre: number[] = Array(n + 1).fill(0);
pre[1] = 1;
const f: boolean[] = Array(n).fill(false);
f[0] = true;
for (let i = 1; i < n; ++i) {
if (s[i] === '0') {
const [l, r] = [Math.max(0, i - maxJump), i - minJump];
f[i] = l <= r && pre[r + 1] - pre[l] > 0;
}
pre[i + 1] = pre[i] + (f[i] ? 1 : 0);
}
return f[n - 1];
}(code-box)
/**
* @param {string} s
* @param {number} minJump
* @param {number} maxJump
* @return {boolean}
*/
var canReach = function (s, minJump, maxJump) {
const n = s.length;
const pre = Array(n + 1).fill(0);
pre[1] = 1;
const f = Array(n).fill(false);
f[0] = true;
for (let i = 1; i < n; ++i) {
if (s[i] === '0') {
const [l, r] = [Math.max(0, i - maxJump), i - minJump];
f[i] = l <= r && pre[r + 1] - pre[l] > 0;
}
pre[i + 1] = pre[i] + (f[i] ? 1 : 0);
}
return f[n - 1];
};(code-box)
