Letter Combinations of a Phone Number - Video Solutions

Problem Overview: Given a string of digits from 2-9, return all possible letter combinations those digits could represent on a classic phone keypad. Each digit maps to multiple characters, and the task is to generate every valid combination in the correct order.

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

This problem maps directly to backtracking. Each digit expands into multiple possible characters, forming a decision tree where every level corresponds to one digit. Start with the first digit, iterate through its mapped letters, append one character to the current path, and recursively process the next digit. When the path length equals the number of digits, add the built string to the result list. The branching factor is at most 4 (digits like 7 and 9), giving roughly 4^n combinations, and building each string costs O(n). A small hash table or array stores the digit-to-letter mapping. This approach is concise, natural for the problem structure, and commonly expected in interviews.

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

The same combination tree can be generated iteratively using a queue. Start by pushing an empty string into the queue. For each digit in the input, process all current partial combinations: remove a string from the queue, append every possible letter mapped from the current digit, and push the new strings back. After processing all digits, the queue contains every complete combination. This effectively performs a level-by-level traversal of the combination tree, similar to BFS. The algorithm still generates up to 4^n results and builds strings of length n, leading to O(4^n * n) time complexity. The queue stores many intermediate strings, so space usage grows to O(4^n).

Both approaches rely on simple string construction and a digit-to-character lookup table. Backtracking builds combinations depth-first using recursion, while BFS expands them iteratively layer by layer.

Recommended for interviews: Recursive backtracking is the expected solution. It mirrors the natural combinatorial structure of the keypad mapping and uses minimal extra memory. BFS works as well and shows strong understanding of iterative state expansion, but interviewers usually look for the backtracking pattern when exploring all combinations of choices.