Knight on the Keypad
A phone keypad has the rows 1 2 3, 4 5 6 and 7 8 9, plus a bottom row with only 0, under the 8. A chess knight starts on any key and dials it, then makes length - 1 knight moves (two keys in a straight line, then one key to the side), dialing every key it lands on. It may never use a key listed in broken, not even as its first key.
Return how many different digit strings of length digits the knight can dial, modulo 1,000,000,007.
Example 1
Every key except 5 has two or three knight moves, and together they make 20 two-digit strings, such as 16, 40 and 94.
Example 2
Only 0, 4 and 6 still connect: 4 and 6 jump to 0, and 0 jumps to 4 or 6. That gives 040, 060, 404, 406, 604 and 606.
Constraints
1 <= length <= 2000 <= len(broken) <= 10brokenholds distinct digits from 0 to 9
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Letter DecodingsMedium
- Lightest Deletions to MatchMedium
- Longest Climbing ChainMedium
- Longest Insertion LadderMedium
- Longest Mirror SubsequenceMedium
- Loot Around the Lantern RingMedium
- Lowest Photo WallMedium
- Lucky Toll TripsMedium