744. Ranged Leaps
A row of stepping platforms is described by the string s: '0' is a solid platform and '1' is a broken one. A courier starts on index 0 and wants to reach the last index.
From index i the courier may leap to any index j that is a solid platform and satisfies i + minJump <= j <= i + maxJump, staying inside the row. Return true if the last index can be reached, otherwise false.
If the first or last character is '1' the answer is false. If the row has a single solid platform the courier is already at the end, so return true. If minJump > maxJump and the row has more than one platform, no leap exists, so return false.
Aim for time O(n) and space O(n).
Example 1
- Input:
- s = "0010100", minJump = 2, maxJump = 3
- Output:
- true
- Explanation:
Index 0 can leap to 3 (solid) and then from 3 to 6, which is the last index, so the answer is true.
Example 2
- Input:
- s = "0110110", minJump = 1, maxJump = 2
- Output:
- false
- Explanation:
Every move of at most 2 lands on a broken platform at some point: from 0 only index 1 or 2 is allowed and both are broken, so the answer is false.
Example 3
- Input:
- s = "00000", minJump = 3, maxJump = 3
- Output:
- false
- Explanation:
From 0 the only leap lands on 3, and from 3 the next leap would be 6, outside the row, so the end index 4 is unreachable: false.
Constraints
1 ≤ s.length ≤ 105
s contains only '0' and '1'
1 ≤ minJump, maxJump ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)