- Convert the string into a char array so reachable positions can be modified directly.
- Start from index 0, since it is the starting reachable position.
-
Whenever the current index is reachable (i == 0 or marked as '2'):
- Try all jumps from i + minJump to i + maxJump.
- If a target position contains '0', mark it as '2' meaning “this index is reachable”.
j is not reset every time, so already checked ranges are skipped, helping achieve efficient traversal.
In the end, if the last index became '2', it means we successfully reached the end.
class Solution {
public boolean canReach(String A, int minJump, int maxJump) {
char[] s = A.toCharArray();
int i = 0, j = 0;
for (i = 0; i < s.length; ++i)
if (i == 0 || s[i] == '2')
for (j = Math.max(j, i + minJump); j <= Math.min((int) s.length - 1, i + maxJump); j++)
if (s[j] == '0') s[j] = '2';
return s[s.length - 1] == '2';
}
// O(N) time O(N) space
public boolean canReach2(String A, int min, int max) {
int N = A.length();
boolean[] dp = new boolean[N];
dp[0] = true;
// cum: cumulated number of valid jump-from index in in [i - maxJump, i - minJump].
int cum = 0;
for (int i = min; i < N; ++i) {
if (dp[i - min]) cum++;
if (i - max - 1 >= 0 && dp[i - max - 1]) cum--;
dp[i] = A.charAt(i) == '0' && cum >= 1;
}
return dp[N - 1];
}
}
