Letter Combinations of a Phone Number - Video Solutions

Problem Overview: You receive a string of digits from 2–9 representing keys on a traditional phone keypad. Each digit maps to multiple letters. The task is to generate every possible letter combination the digits could represent.

Approach 1: Recursive Backtracking (O(4^n * n) time, O(n) auxiliary space)

Backtracking models the problem as a decision tree. Each digit expands into 3 or 4 possible letters. Start from the first digit and recursively append each mapped letter to a temporary string. Move to the next digit until the combination length equals the number of digits, then store the result. The key insight is treating each digit as a level in the recursion tree and exploring all branches. The recursion depth is n, where n is the number of digits, and each level may branch up to 4 times, leading to O(4^n) combinations. This approach naturally fits problems involving backtracking and recursive state exploration.

A lookup structure maps digits to characters (for example using a dictionary or array). At each recursive step you iterate through the mapped characters and append one to the current path. After exploring a branch, remove the last character and continue with the next option. This systematic exploration guarantees every valid combination is generated exactly once.

Approach 2: Iterative Breadth-First Search (BFS) (O(4^n * n) time, O(4^n * n) space)

The BFS approach builds combinations level by level instead of using recursion. Start with a queue containing an empty string. For each digit, remove all existing partial combinations from the queue and append every possible mapped letter for that digit. Push the newly formed strings back into the queue. After processing all digits, the queue holds every valid combination.

This method mirrors a breadth-first traversal of the implicit combination tree. Each iteration expands the current level using the mapping table, which is typically stored in a simple array or hash table. The total number of generated strings is still bounded by 4^n, and each combination requires copying up to n characters, giving O(4^n * n) time complexity. Since all intermediate combinations are stored in the queue, the space usage grows with the number of generated results.

The BFS style can feel more intuitive if you prefer iterative solutions over recursion. It also avoids recursion stack limits while still relying heavily on efficient string construction.

Recommended for interviews: Recursive backtracking is the approach most interviewers expect. It demonstrates comfort with recursion, state management, and combinatorial search. BFS works just as well but mainly shows an alternative iterative mindset. Mentioning both approaches signals strong algorithmic understanding.