How to Solve: Letter Combinations of a Phone Number

How to Solve: Letter Combinations of a Phone Number

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem tests your ability to generate all possible combinations efficiently—a pattern that appears in 1 out of every 3 onsite interviews at FAANG. Master it, and you’ll prove you can handle backtracking, recursion, and edge cases under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Backtracking (DFS) – Recursively exploring all possible paths and backtracking when a path is exhausted. 2. Hash Maps (Dictionaries) – Mapping digits to their corresponding letters (e.g., '2' → ['a', 'b', 'c']). 3. String Manipulation – Concatenating characters and building strings dynamically.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every problem of this type.)

1. Clarify Input & Output
2. Input: A string of digits ("23").
3. Output: List of all possible letter combinations (["ad","ae","af","bd","be","bf","cd","ce","cf"]).

4. Edge cases: Empty string (""), digits '0' or '1' (no letters).

5. Precompute Digit-to-Letter Mapping

6. Create a dictionary:
   python
digit_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}

7. Choose an Approach: Backtracking (DFS) or BFS

8. Backtracking (DFS):
   • Recursively build combinations by appending each letter of the current digit.
   • Backtrack by removing the last letter when returning from recursion.

9. BFS (Iterative):

   • Use a queue to build combinations level by level.
   • Start with "", then append letters of the first digit, then the next, etc.

10. Implement the Chosen Approach

11. DFS:
    • Base case: If the current combination length equals the input digits length, add to result.
    • Recursive case: For each letter of the current digit, append it and recurse.

12. BFS:

    • Initialize queue with "".
    • For each digit, dequeue all current combinations, append each letter, and enqueue.

13. Handle Edge Cases

14. If input is "", return [].

15. If input contains '0' or '1', skip (no letters).

16. Optimize Time & Space

17. Time: O(4^n) (worst case, e.g., "777" → 4^3 = 64 combinations).

18. Space: O(n) (DFS recursion stack) or O(4^n) (BFS queue).

19. Test with Examples

20. Test with "23", "", "2", "79" (includes '7' and '9' with 4 letters each).

? WORKED EXAMPLES

Example 1 – Basic (Backtracking DFS)

Problem: Given "23", return all possible letter combinations.

Thought Process: 1. Map '2' → 'abc', '3' → 'def'. 2. Start with "", then append 'a', 'b', 'c' recursively. 3. For each, append 'd', 'e', 'f' and add to result.

Code (Python):

def letterCombinations(digits):

    if not digits:

        return []


    digit_map = {

        '2': 'abc',

        '3': 'def',

        '4': 'ghi',

        '5': 'jkl',

        '6': 'mno',

        '7': 'pqrs',

        '8': 'tuv',

        '9': 'wxyz'

    }


    result = []


    def backtrack(index, current_combination):

        if index == len(digits):

            result.append(current_combination)

            return


        current_digit = digits[index]

        for letter in digit_map[current_digit]:

            backtrack(index + 1, current_combination + letter)


    backtrack(0, "")

    return result

Time Complexity: O(4^n) (each digit has up to 4 letters, and we explore all combinations). Space Complexity: O(n) (recursion stack depth = number of digits).

Why This Works: - Backtracking explores all paths by appending each letter of the current digit and recursing. - The base case (index == len(digits)) ensures we only add complete combinations.

Example 2 – Medium (BFS Iterative)

Problem: Same as above, but implement using BFS (queue).

Thought Process: 1. Start with "" in the queue. 2. For each digit, dequeue all current combinations, append each letter, and enqueue. 3. Repeat until all digits are processed.

Code (Python):

from collections import deque

def letterCombinations(digits):

    if not digits:

        return []


    digit_map = {

        '2': 'abc',

        '3': 'def',

        '4': 'ghi',

        '5': 'jkl',

        '6': 'mno',

        '7': 'pqrs',

        '8': 'tuv',

        '9': 'wxyz'

    }


    queue = deque([""])

    result = []


    for digit in digits:

        level_size = len(queue)

        for _ in range(level_size):

            current = queue.popleft()

            for letter in digit_map[digit]:

                queue.append(current + letter)


    return list(queue)

Time Complexity: O(4^n) (same as DFS). Space Complexity: O(4^n) (queue stores all combinations at each level).

Why This Works: - BFS builds combinations level by level, ensuring all possibilities are explored. - The queue dynamically grows as we append letters, then shrinks as we process them.

Example 3 – Hard/Follow-Up (Memoization + Early Pruning)

Problem: Given "23", return combinations without duplicates (e.g., if '2' maps to 'aab' instead of 'abc').

Thought Process: 1. Modify digit_map to allow duplicate letters (e.g., '2': 'aab'). 2. Use a set to avoid duplicate combinations. 3. Prune early if a letter has already been used in the current path.

Code (Python):

def letterCombinations(digits):

    if not digits:

        return []


    digit_map = {

        '2': 'aab',  # Example with duplicates

        '3': 'def'

    }


    result = set()  # Avoid duplicates


    def backtrack(index, current_combination):

        if index == len(digits):

            result.add(current_combination)

            return


        current_digit = digits[index]

        for letter in digit_map[current_digit]:

            backtrack(index + 1, current_combination + letter)


    backtrack(0, "")

    return list(result)

Time Complexity: O(4^n) (worst case, but pruning reduces actual runtime). Space Complexity: O(n) (recursion stack) + O(4^n) (set storage).

Why This Works: - Set ensures no duplicates in the result. - Backtracking still explores all paths, but the set filters out repeats.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Here’s your 60-second recap:

1. Map digits to letters – Precompute digit_map once.
2. Choose DFS or BFS –
3. DFS (backtracking): Recursively build combinations, backtrack after each digit.
4. BFS (queue): Start with "", append letters level by level.
5. Handle edge cases – Empty input? Return []. Digits '0' or '1'? Skip them.
6. Time complexity is O(4^n) – Each digit has up to 4 letters, and we explore all combinations.
7. Space complexity – O(n) for DFS (recursion stack), O(4^n) for BFS (queue).

Now go crush that interview. You’ve got this!

? Final Notes

• Practice Variations:
• LeetCode 17. Letter Combinations of a Phone Number
• LeetCode 22. Generate Parentheses (similar backtracking pattern).
• Key Insight: This problem is a classic backtracking question. Mastering it prepares you for subsets, permutations, and combinations problems.