Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1871.html
1871. Jump Game VII
Level
Medium
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 <= 10^5s[i]is either'0'or'1'.s[0] == '0'1 <= minJump <= maxJump < s.length
Solution
Use a list to store the indices that have characters ‘0’ in s. Then use two pointers curr and next to mark the indices that can be reached. Initially, index 0 can be reached and curr = 0. For each curr, find the range of next such that curr + minJump <= next <= curr + maxJump and next < s.length(). Since both curr and next can only move forward, the two pointers can only loop over all indices once. Finally, return true if and only if the index s.length() - 1 can be reached.
-
class Solution { public boolean canReach(String s, int minJump, int maxJump) { List<Integer> indices = new ArrayList<Integer>(); int length = s.length(); if (s.charAt(length - 1) != '0') return false; for (int i = 0; i < length; i++) { if (s.charAt(i) == '0') indices.add(i); } int size = indices.size(); boolean[] visited = new boolean[size]; visited[0] = true; int curr = 0, next = 0; while (curr < size) { while (curr < size && !visited[curr]) curr++; if (curr == size) return false; int currIndex = indices.get(curr); while (next < size && indices.get(next) - currIndex < minJump) next++; while (next < size && indices.get(next) - currIndex <= maxJump) { visited[next] = true; next++; } curr++; } return visited[size - 1]; } } ############ class Solution { public boolean canReach(String s, int minJump, int maxJump) { int n = s.length(); boolean[] dp = new boolean[n]; dp[0] = true; int[] preSum = new int[n + 1]; preSum[1] = 1; for (int i = 1; i < n; ++i) { if (s.charAt(i) == '0') { int l = Math.max(0, i - maxJump); int r = i - minJump; if (r >= l && preSum[r + 1] - preSum[l] > 0) { dp[i] = true; } } preSum[i + 1] = preSum[i] + (dp[i] ? 1 : 0); } return dp[n - 1]; } } -
// OJ: https://leetcode.com/problems/jump-game-vii/ // Time: O(N) // Space: O(maxJump - minJump) class Solution { public: bool canReach(string s, int minJump, int maxJump) { if (s.back() == '1') return false; queue<int> q; int j = 0, prev = 0; for (int i = 1; i < s.size(); ++i) { if (i - prev > maxJump) return false; if (s[i] == '1') continue; j = max(j, i - maxJump); while (i - j >= minJump) { if (s[j] == '0') q.push(j); ++j; } while (q.size() && i - q.front() > maxJump) q.pop(); if (q.empty()) s[i] = '1'; // mark this position as non-reachable. else prev = i; } return q.size(); } }; -
class Solution: def canReach(self, s: str, minJump: int, maxJump: int) -> bool: n = len(s) dp = [False] * n dp[0] = True pre_sum = [0] * (n + 1) pre_sum[1] = 1 for i in range(1, n): if s[i] == '0': l = max(0, i - maxJump) r = i - minJump if r >= l and pre_sum[r + 1] - pre_sum[l] > 0: dp[i] = True pre_sum[i + 1] = pre_sum[i] + dp[i] return dp[n - 1] ############ # 1871. Jump Game VII # https://leetcode.com/problems/jump-game-vii class Solution: def canReach(self, s: str, minJump: int, maxJump: int) -> bool: n = len(s) visited, mx = set([0]), 0 queue = collections.deque([0]) while queue: i = queue.popleft() for j in range(max(i + minJump, mx + 1), min(i + maxJump + 1, n)): if s[j] == "0" and j not in visited: if j == n - 1: return True queue.append(j) visited.add(j) mx = max(mx, i + maxJump) return False -
/** * @param {string} s * @param {number} minJump * @param {number} maxJump * @return {boolean} */ var canReach = function (s, minJump, maxJump) { let n = s.length; let dp = new Array(n).fill(0); let sum = new Array(n + 1).fill(0); dp[0] = 1; sum[1] = 1; for (let i = 1; i < n; i++) { if (s.charAt(i) == '0') { let left = Math.max(0, i - maxJump); let right = i - minJump; if (left <= right && sum[right + 1] - sum[left] > 0) { dp[i] = 1; } } sum[i + 1] = sum[i] + dp[i]; } return dp.pop(); }; -
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] } -
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]; }