LeetCode #935 Knight Dialer

Medium

Problem

A chess knight can move as indicated in the chess diagram below:

.

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops. Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

Example 1:

Input: 1
Output: 10

Example 2:

Input: 2
Output: 20

Example 3:

Input: 3
Output: 46

Note:

• 1 <= N <= 5000

Solution — DFS

It’s trivial that we can use DFS to count all possible numbers. However, it’s too slow that will reach the time limit of LeetCode.

Complexity

The move subroutine will not stop until N is one, which means it will be executed 10 + 8 * (N — 1) times. Therefore, its time complexity is O(n).

For space complexity, it depends on execution times of move subroutine, so its space complexity is O(n) as well.

Solution — Dynamic Programming

Let’s consider how number 1 will be visited. Obviously it can go from number 6 or number 8. And number 4 can be visited by number 0, 3 and 9. By this observation, we can use dynamic programming approach on this problem.

Complexity

It takes O(N-1) time on line 17, and O(10) time on line 19. On line 20, it will not be run over 3 times. Therefore, its time complexity is O(N).

For space complexity, result and nextResult only take O(10) extra space. Hence we can say it only needs O(1) extra space.

Follow Up

If you don’t use Python on this problem, please be aware of overflow issue.