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 \in [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$.
1
2
3
4
5
6
7
8
9
10
11
12
| 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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /**
* @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];
};
|
