Leetcode QOTD:- 1871. Jump Game VII

• 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];
  }
}