from typing import List
class Solution:
def canCross(self, stones: List[int]) -> bool:
N = len(stones)
d = {}
if stones[1] != 1: # if we cannot jump at initial place, it definitely False
return False
# build value-index mapping
for i, stone in enumerate(stones):
d[stone] = i
# dp is the number of jumps to location i
# for example, we can only jump to pos 1 with 1 units
# if we can jump to pos X for {a, b, c} units, it means that we can jump to X for a, b, c units
# it also means that from pos X, we can jump for <a-1, a, a+1, b-1, b, b+1, c-1, c, c+1> units.
dp = [{0}, {1}]
for i in range(2, N):
dp.append(set())
for i in range(1, N):
s = stones[i]
for k in dp[i]:
# do jump
# if k-1 is ok for position stones[i], jump and add to dp
if s + k - 1 in d and k - 1 != 0:
dp[d[s + k - 1]].add(k - 1)
# if k is ok for position stones[i], jump and add to dp
if s + k in d and k != 0:
dp[d[s + k]].add(k)
# if k+1 is ok for position stones[i], jump and add to dp
if s + k + 1 in d and k + 1 != 0:
dp[d[s + k + 1]].add(k + 1)
return len(dp[-1]) != 0
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)