Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Expand one keypad group per position: The Phone Letters.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Phone letter combinations matches the clues
- 2Keep this true after every move: path has exactly one mapped letter for every processed digit
- 3Reach the result within O(4^n times n) output time
Rules and pressure
- Target cost: O(4^n times n) output time
- State rule: path has exactly one mapped letter for every processed digit
Lesson 1 of 3
Live algorithm trace
Phone letter combinations
Complete execution1 of 5
2
digit
3
a
d
e
f
The first depth expands letters a, b, and c for digit 2.
1
if digits empty: return empty list2
search(digit index)3
if all digits consumed: record4
for each mapped letter5
append, recurse to next digit6
undodigits = 23path =
Truth to preserve / Cost target
Truth to preserve
path has exactly one mapped letter for every processed digit
Cost target
O(4^n times n) output time
Each digit owns a small candidate alphabet. Recursion fills one output position from that alphabet, producing the Cartesian product without retaining a full intermediate product.
Your call · What should guide every step of this algorithm?