(This question is a variation of the LeetCode question 1197. Minimum Knight Moves. If you haven't completed that question yet, it is recommended to solve it first.)
You're given a phone-style numeric keypad:
1 2 3
4 5 6
7 8 9
0
A chess knight moves in an "L" shape: two squares in one direction (up/down/left/right) and then one square perpendicular. A move is valid only if it lands on another digit shown on the keypad (moves that go off the layout are not allowed). For instance, from '1' the knight can jump only to '6' or '8'.
Your goal is to return all unique digit sequences where the knight starts at digit start, makes exactly moves valid knight jumps, and finishes at digit end. Each sequence should include the starting digit, so its length will be moves + 1. You may return the result in any order.
Constraints:
- 0 ≤
moves≤ 10
Example 1:
Input: start = 1, end = 9, moves = 4 Output: ["16049", "16729", "18349"] Explanation: Starting from digit '1', there are three valid paths to reach digit '9' in exactly 4 moves:
- Path 1: 1 → 6 → 0 → 4 → 9 (forms number "16049")
- Path 2: 1 → 6 → 7 → 2 → 9 (forms number "16729")
- Path 3: 1 → 8 → 3 → 4 → 9 (forms number "18349")
All three paths follow valid knight moves on the keypad and end at digit '9'.
Example 2:
Input: start = 1, end = 9, moves = 2 Output: []
Example 3:
Input: start = 0, end = 0, moves = 2 Output: ["040", "060"]
