Skip to content

1871. Jump Game VII 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  bool canReach(string s, int minJump, int maxJump) {
    int count = 0;
    vector<bool> dp(s.length());
    dp[0] = true;

    for (int i = minJump; i < s.length(); ++i) {
      count += dp[i - minJump];
      if (i - maxJump > 0)
        count -= dp[i - maxJump - 1];
      dp[i] = count && s[i] == '0';
    }

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public boolean canReach(String s, int minJump, int maxJump) {
    int count = 0;
    boolean dp[] = new boolean[s.length()];
    dp[0] = true;

    for (int i = minJump; i < s.length(); ++i) {
      count += dp[i - minJump] ? 1 : 0;
      if (i - maxJump > 0)
        count -= dp[i - maxJump - 1] ? 1 : 0;
      dp[i] = count > 0 && s.charAt(i) == '0';
    }

    return dp[dp.length - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
    count = 0
    dp = [True] + [False] * (len(s) - 1)

    for i in range(minJump, len(s)):
      count += dp[i - minJump]
      if i - maxJump > 0:
        count -= dp[i - maxJump - 1]
      dp[i] = count and s[i] == '0'

    return dp[-1]