Frog Jump LeetCode solution in Python

1
# Runtime: 231 ms (Top 72.60%) | Memory: 19.2 MB (Top 61.18%)
2
class Solution:
3
    def possible(self, i, n, stones, pos, allowedJumps):
4
        if i == n - 1:
5
            return True
6
        key = tuple([i] + allowedJumps)
7
        if key in self.cache:
8
            return self.cache[key]
9
        for jump in allowedJumps:
10
            if jump > 0 and stones[i] + jump in pos:
11
                if self.possible(
12
                    pos[stones[i] + jump], n, stones, pos, [jump - 1, jump, jump + 1]
13
                ):
14
                    self.cache[key] = True
15
                    return True
16
        self.cache[key] = False
17
        return False
18

19
    def canCross(self, stones: List[int]) -> bool:
20
        n = len(stones)
21
        pos = {}
22
        for i, stone in enumerate(stones):
23
            pos[stone] = i
24
        self.cache = {}
25
        return self.possible(0, n, stones, pos, [1])