Given a string of digits from 2 to 9, return all letter combinations they could represent on a phone keypad (2 is abc, 3 is def, … 7 is pqrs, 9 is wxyz).
Before you code
Each digit is one level of the search tree, and its letters are the choices at that level. The result has up to 4ⁿ strings for n digits.
Hints
- Recurse with the index of the next digit and the letters chosen so far.
- When the index reaches the end, record the string.
- An empty input returns an empty list, not a list with one empty string.
Production & complexity notes
When solving Letter combinations of a phone number on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Backtracking basics to reinforce the underlying pattern.
What it practices
The choose, explore, unchoose pattern and pruning, from Backtracking basics.