Knight Dialer LeetCode solution in Python

1
class Solution:
2
    MOD = 10**9 + 7
3

4
    def knightDialer(self, n: int) -> int:
5
        # Initialize an array to store the possible positions of the knight on the phone pad
6
        cur_pos = [1] * 10
7

8
        # Loop through the number of jumps required
9
        for jump in range(2, n + 1):
10
            # Create a new list to store the updated positions after each jump
11
            new_pos = [0] * 10
12

13
            # Calculate the new positions based on the valid knight moves
14
            new_pos[0] = (cur_pos[6] + cur_pos[4]) % self.MOD
15
            new_pos[1] = (cur_pos[6] + cur_pos[8]) % self.MOD
16
            new_pos[2] = (cur_pos[7] + cur_pos[9]) % self.MOD
17
            new_pos[3] = (cur_pos[4] + cur_pos[8]) % self.MOD
18
            new_pos[4] = (cur_pos[0] + cur_pos[3] + cur_pos[9]) % self.MOD
19
            new_pos[5] = 0  # Knight cannot move to position 5
20
            new_pos[6] = (cur_pos[0] + cur_pos[1] + cur_pos[7]) % self.MOD
21
            new_pos[7] = (cur_pos[2] + cur_pos[6]) % self.MOD
22
            new_pos[8] = (cur_pos[1] + cur_pos[3]) % self.MOD
23
            new_pos[9] = (cur_pos[2] + cur_pos[4]) % self.MOD
24

25
            # Update the current positions list for the next iteration
26
            cur_pos = new_pos
27

28
        # Calculate the total count of distinct phone numbers
29
        total_count = sum(cur_pos) % self.MOD
30

31
        return total_count