Letter Combinations of a Phone Number
WHAT IT SAYS
Given a string of digits from 2 to 9, return every letter combination the number could spell on a phone keypad.
WHAT IT'S REALLY ASKING
"Digit 2 does not care what digit 3 becomes. There is no rule connecting one position to another — which means this is not a search with dead ends, it is a cartesian product. The only question left is whether you would rather walk it with a recursion or an odometer."
Generate all strings, keep the legal ones
O(26^L * L) timeBuild every string of length L over the 26 letters, then keep the ones where each character happens to belong to its digit's keypad set.
WHERE THE WORK IS WASTED — For four digits you construct roughly 457,000 strings to keep at most 81 of them. And the filter is doing something absurd: the legality of position i depends on NOTHING but position i, so it was decidable the instant you wrote that character down. You are deferring a per-character check to the end of a whole word, and paying an exponential multiplier for the delay.
No position constrains another, so nothing is ever rejected.
Look for a cross-position constraint in this problem. There is none. Position i draws from the letter set of digit i, and no other position has an opinion about it. When the choices at each position are independent, the set of answers is exactly the cartesian product of the per-position option sets. That is a counting identity — the answer count is the product of the set sizes, known before you start — and it is also a construction: walk the positions in order, and at each one branch over its options. Here is what makes this problem worth its own file rather than being a footnote to Generate Parentheses. In Generate Parentheses, an early choice can kill a later one, so the tree is full of dead branches and the entire skill is pruning them. Here the tree has NO dead branches. Every path from the root to a leaf is a valid answer. Any validity check you write is dead code; any pruning you add will never fire. The cost of the algorithm equals the size of its output, which is the theoretical floor. So the recursion is not really a search — it is an odometer with a different digit-base at each wheel. That is also why the iterative solution works so cleanly: start with a list containing the empty string and, for each digit, replace the list with every existing string extended by every letter of that digit. Same product, built breadth-first instead of depth-first.
Walk the product, position by position
O(product of the option counts, times L) — exactly the output size, which is optimalRecurse on the digit index carrying the string built so far. At index i, loop over the letters of that digit, append, recurse on i+1, and pop. When the index runs off the end, the string is complete — record it, no check required. Handle the empty input as its own case: zero digits means zero combinations, not one empty string.
Cartesian Product, No Dead Ends
YOU'LL SEE IT AGAIN WHEN
- Each position draws from its own fixed menu, and no choice constrains any other position.
- The output size is exactly the product of the option counts, so you can predict it before writing any code.
- Every leaf of the recursion is a valid answer — meaning any validity check or pruning in your template will never once fire.