#403

Frog Jump

candidate master · 1500 · lc hard +32 · verified · 47.1% accepted · 5,973 likes · top 32%

Description

A frog begins on the first stone of a sorted ascending array stones and must cross to the last stone. Its very first jump must be exactly 1 unit. After any jump of size k, the next jump may be k - 1, k, or k + 1 units. The frog can only move forward and may only land on positions listed in stones.

Return true if the frog can reach the final stone, false otherwise.

Example 1:

Input: stones = [0,1,3,5,6,8,12,17]

Output: true

Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

Input: stones = [0,1,2,3,4,8,9,11]

Output: false

Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

Code

1

2

3

class Solution:
    def canCross(self, stones: List[int]) -> bool:

class Solution:
    def canCross(self, stones: List[int]) -> bool: