Letter Combinations of a Phone Number - Solution & Explanation
Problem Statement
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "" Output: []
Example 3:
Input: digits = "2" Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Approach Overview
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.
Approach 1: Recursive Backtracking Approach
This approach uses recursion to explore all possible combinations represented by the digit-to-letter mapping of a phone keypad. We incrementally build letter combinations by allocating one letter per digit, and then explore further by making recursive calls.
The recursion depth is determined by the number of digits and the choices per digit. At each step, the algorithm branches into as many recursive calls as there are letters assigned to the current digit, continuing until all digits have been processed.
This Python solution utilizes a recursive helper method backtrack to explore all combinations by trying each possible letter for each digit sequentially. The base case is when the length of the path equals the number of digits, signifying a complete combination has been constructed. The combinations list accumulates all completed combinations, which is then returned as the result.
Complexity
Time Complexity: O(3^n * 4^m), where n is the number of digits that map to 3 letters, and m is the number of digits that map to 4 letters.
Space Complexity: O(n), the maximum depth of the recursion stack is n.
Approach 2: Iterative Breadth-First Search (BFS) Approach
The iterative BFS approach systematically explores all possible combinations of letter sequences by progressively building up combinations using a queue. It starts by enqueueing an empty string, and then, for each digit from the input, extends through all mapped letters, enqueuing partial solutions until all digits have been processed.
This method mimics the complete depth-first search but layers on combinations iteratively, capitalizing on the breadth search over immediate digit map expansion.
The Python solution leverages a queue (deque) to perform BFS-style exploration of all letter combinations. Initially, it stores an empty string, and iteratively enqueues combinations by appending the letters mapped from current digits. The process continues until all digits have been covered, emerging with a full spectrum of possible sequences.
Complexity
Time Complexity: O(3^n * 4^m), as methodically layers through the digit-letter expansion uniformly across a queue.
Space Complexity: O(n * 3^n * 4^m), where queue storage inflates in tandem with combination depth.
Approach 3: Traversal
First, we use an array or hash table to store the letters corresponding to each digit. Then we traverse each digit, combine its corresponding letters with the previous results to get the new results.
The time complexity is O(4^n), and the space complexity is O(4^n). Here, n is the length of the input digits.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Approach 4: DFS
We can use the method of depth-first search to enumerate all possible letter combinations. Suppose that a part of the letter combination has been generated, but some digits have not been exhausted. At this time, we take out the letters corresponding to the next digit, and then enumerate each letter corresponding to this digit one by one, add them to the letter combination that has been generated before, to form all possible combinations.
The time complexity is O(4^n), and the space complexity is O(n). Here, n is the length of the input digits.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
C
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Backtracking Approach | Time Complexity: O(3^n * 4^m), where n is the number of digits that map to 3 letters, and m is the number of digits that map to 4 letters. Space Complexity: O(n), the maximum depth of the recursion stack is n. |
| Iterative Breadth-First Search (BFS) Approach | Time Complexity: O(3^n * 4^m), as methodically layers through the digit-letter expansion uniformly across a queue. Space Complexity: O(n * 3^n * 4^m), where queue storage inflates in tandem with combination depth. |
| Traversal | — |
| DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(4^n * n) | O(n) | Best for interviews and when generating combinations via DFS recursion |
| Iterative BFS (Queue) | O(4^n * n) | O(4^n) | Useful when you prefer iterative solutions or want level-by-level combination expansion |
Video Solution
Letter Combinations of a Phone Number - Backtracking - Leetcode 17 • NeetCode • 237,557 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Letter Combinations of a Phone Number easy or hard?
Letter Combinations of a Phone Number Python/Java solution
How to solve Letter Combinations of a Phone Number in O(n)?
What is the best approach for Letter Combinations of a Phone Number?
Is Letter Combinations of a Phone Number asked at Google/Amazon/Meta?
What data structure is used in Letter Combinations of a Phone Number?
What is the time complexity of Letter Combinations of a Phone Number?
Ready to solve this problem?
Practice Letter Combinations of a Phone Number with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor