Letter Combinations of a Phone Number

Letter Combinations of a Phone Number

What is this problem about?

The "Letter Combinations of a Phone Number interview question" is one of the most famous coding challenges. Given a string of digits from 2-9 inclusive (like on a phone keypad), you need to return all possible letter combinations that the number could represent. Each digit maps to a set of letters (e.g., 2 -> "abc", 3 -> "def"). This "Letter Combinations of a Phone Number coding problem" is the quintessential backtracking exercise.

Why is this asked in interviews?

Virtually every major tech company, from Google to Amazon, has asked this question. It tests your ability to handle "Backtracking interview pattern" logic and "Hash Table interview pattern" (for mapping digits to letters). It also evaluates your ability to handle recursive branching and nested structures, which are fundamental to complex software systems.

Algorithmic pattern used

Backtracking is the standard approach. You use a hash map to store the digit-to-letter mappings. Then, you use a recursive function that takes the current combination and the index of the digit being processed. For the current digit, you loop through its corresponding letters, append one to the combination, and recurse for the next index. After the recursion returns, you backtrack (remove the character) to try the next letter.

Example explanation

Digits: "23"

1. Digit '2': Maps to 'a', 'b', 'c'.
2. Pick 'a', move to digit '3' ('d', 'e', 'f').
3. Combinations: "ad", "ae", "af".
4. Backtrack to '2', pick 'b'.
5. Combinations: "bd", "be", "bf".
6. Backtrack to '2', pick 'c'.
7. Combinations: "cd", "ce", "cf".

Common mistakes candidates make

• Base case errors: Not properly handling empty input strings (should return an empty list, not a list with an empty string).
• Inefficient string building: Using string concatenation in a loop instead of a StringBuilder or list of characters.
• Mapping errors: Mistyping the keypad mappings (e.g., 7 and 9 have four letters, while others have three).

Interview preparation tip

This is a "must-know" problem. If you can explain and implement this clearly, you demonstrate a solid grasp of recursive thinking. Pay attention to how the recursion depth matches the length of the input string.