Count All Possible Routes LeetCode solution in Python

1
# Runtime: 3516 ms (Top 53.70%) | Memory: 22.1 MB (Top 43.52%)
2

3
from bisect import bisect_left
4
from functools import lru_cache
5

6

7
class Solution:
8
    def countRoutes(
9
        self, locations: List[int], start: int, finish: int, fuel: int
10
    ) -> int:
11
        start = locations[start]
12
        end = locations[finish]
13
        locations.sort()
14
        start = bisect_left(locations, start)
15
        end = bisect_left(locations, end)
16

17
        @lru_cache(None)
18
        def dfs(i, fuel):
19
            if fuel == 0 and i == end:
20
                return 1
21
            res = 0
22
            if i == end:
23
                res += 1
24
            j = i - 1
25
            while j >= 0 and abs(locations[j] - locations[i]) <= fuel:
26
                res += dfs(j, fuel - abs(locations[j] - locations[i]))
27
                j -= 1
28
            j = i + 1
29
            while j < len(locations) and abs(locations[j] - locations[i]) <= fuel:
30
                res += dfs(j, fuel - abs(locations[j] - locations[i]))
31
                j += 1
32
            return res
33

34
        return dfs(start, fuel) % (10**9 + 7)