Jump Game VII

Medium

Strings Dynamic Programming BFS (Breadth-First Search)Sliding Window Dynamic Programming

Problem

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.

Constraints

2 <= s.length <= 10^5
s[i] is either '0' or '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

Examples

Input: s = "011010", minJump = 2, maxJump = 3

Output: true

In the first step, move from index 0 to index 3. In the second step, move from index 3 to index 5.

Input: s = "01101110", minJump = 2, maxJump = 3

Output: false

There is no way to reach the last index starting from index 0.

Loading...

Loading Python...