Show problems as
Classic problem #1871MediumStringDynamic ProgrammingSliding WindowPrefix Sum

Jump Game VII

Real-world version: Pontoon Crossing With A Hop Range
Tracked in this browser only
Read Jump Game VII on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A temporary walkway across a channel is described by s, one character per pontoon along the line. '0' marks a pontoon that still floats and can be stood on, '1' marks one that has gone under and cannot.

A surveyor starts on pontoon 0, which always floats. From the pontoon at index i the surveyor may hop to the pontoon at index j when all of the following hold:

  • i + minJump <= j <= i + maxJump,
  • j is within the walkway, so j <= s.length - 1,
  • s[j] is '0'.

Hops are always forward and there is no limit on how many are taken.

Return true if the surveyor can arrive at the last pontoon, index s.length - 1, and false if no series of hops gets there.

Examples

Example 1

Input
s = "01000110", minJump = 2, maxJump = 3
Output
true

Hopping 0 -> 2 -> 4 -> 7 uses spans of 2, 2 and 3, and pontoons 2, 4 and 7 all float, so the far side is reached.

Example 2

Input
s = "0010", minJump = 2, maxJump = 2
Output
false

Every hop covers exactly two pontoons, so the only landing from pontoon 0 is pontoon 2, which is under water, and the surveyor is stuck at the start.

Example 3

Input
s = "0110", minJump = 3, maxJump = 3
Output
true

A single hop of three lands directly on pontoon 3, which floats.

Example 4

Input
s = "00001", minJump = 1, maxJump = 2
Output
false

The last pontoon is submerged, so it cannot be stood on and the crossing fails.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def can_cross_channel(deck: str, min_span: int, max_span: int) -> bool:
Java
public boolean canCrossChannel(String deck, int minSpan, int maxSpan)

More on the same topics