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), and
s[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.
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$.