Numbers With Same Consecutive Differences LeetCode solution in Python

1
class Solution:
2
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
3
        # initialize the cache with all the valid numbers of length 1
4
        # cache is a list of tuple (number, digit at units place)
5
        cache = [
6
            (0, 0),
7
            (1, 1),
8
            (2, 2),
9
            (3, 3),
10
            (4, 4),
11
            (5, 5),
12
            (6, 6),
13
            (7, 7),
14
            (8, 8),
15
            (9, 9),
16
        ]
17
        cacheTemp = []
18

19
        # each iteration will store all the valid numbers of length 2 to n in cache
20
        for i in range(2, n + 1):
21
            # loop through the cache from the previous iteration
22
            for j in cache:
23
                if k == 0:
24
                    if j[0] != 0:
25
                        cacheTemp.append((j[0] * 10 + j[1], j[1]))
26
                elif j[1] == 0 and i == 2:
27
                    continue
28
                elif j[1] <= k - 1:
29
                    if j[1] < 10 - k:
30
                        cacheTemp.append((j[0] * 10 + j[1] + k, j[1] + k))
31
                elif j[1] >= 10 - k:
32
                    if j[1] > k - 1:
33
                        cacheTemp.append((j[0] * 10 + j[1] - k, j[1] - k))
34
                else:
35
                    cacheTemp.append((j[0] * 10 + j[1] - k, j[1] - k))
36
                    cacheTemp.append((j[0] * 10 + j[1] + k, j[1] + k))
37
            cache = cacheTemp  # store the list of valid integers of length i in cache
38
            cacheTemp = []  # empty the temporary list
39

40
        res = []
41
        for i in cache:
42
            res.append(i[0])
43

44
        return res