DSA interview question

Letter Combinations of a Phone Number

Hard · Algorithms · Topics: recursion, backtracking, string

The problem

An old-school phone keypad maps each digit from 2 to 9 to a few letters (2 → abc, 3 → def, …, 7 → pqrs, 9 → wxyz). A contact-search feature takes the digits a user presses and must suggest every letter string those digits could spell, so it can match them against names. Each digit contributes one letter, so the answer is the Cartesian product of the digits' letter groups. Backtracking builds it one position at a time.

Example: "23" → ad ae af bd be bf cd ce cf.

Function signature

vector<string> letterCombinations(const string& digits);  // digits 2-9; empty input gives an empty list

Test cases

Input	Output	Explanation
`"23"`	`ad ae af bd be bf cd ce cf`	3 · 3 = 9
`""`	`[]`	No digits, no combinations
`"2"`	`a b c`
`"79"`	16 strings, `pw` … `sz`	4 · 4
`"234"`	27 strings, `adg` … `cfi`	3 · 3 · 3

(Confirm: digits are 2–9 only; an empty input returns an empty list, not [""]; any order is acceptable, keypad order is shown.)

How interviewers phrase it

"Given a string of digits 2-9, return all possible letter combinations the number could represent" (LeetCode 17).

Clarifying questions to ask

Can the input contain 0 or 1? (No; they map to no letters.)
What should an empty input return? (An empty list.)
Does the output order matter?

Follow-ups to expect

"How many results are there?"
"Recursive or iterative?"
"Why is the empty input special?"
"Complexity?"
"How would you only count them?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview