17. Letter Combinations of a Phone Number - Detailed Explanation
Problem statement
Given a string of digits from 2 to 9, return all possible letter combinations that the number could represent. Each digit maps to a set of letters according to the telephone keypad layout, as on old mobile phones or landline phones. The mapping is 2 -> "abc", 3 -> "def", 4 -> "ghi", 5 -> "jkl", 6 -> "mno", 7 -> "pqrs", 8 -> "tuv", and 9 -> "wxyz". The order of the output combinations does not matter. If the input is an empty string, return an empty list.
Many telephone keypads have letters printed on the number keys. This standard mapping places ABC on 2, DEF on 3, GHI on 4, JKL on 5, MNO on 6, PQRS on 7, TUV on 8, and WXYZ on 9. A sequence of digits can therefore represent a sequence of letters. This problem asks us to generate every letter sequence that a given digit string could represent, which is the full set of "phonewords" for that number.
Constraints
0 <= digits.length <= 4. (Since each digit maps to at most 4 letters, the maximum number of combinations is 4^4 = 256.)- The input consists only of digits
'2'through'9'. (Digits'0'and'1'do not map to letters and are not included in the input.)
Example
Example 1
- Input:
"23" - Output:
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] - Explanation: Digit
'2'maps to"abc"and'3'maps to"def". All possible two-letter combinations from those sets are listed.
(Additional examples: An input of "2" would output ["a","b","c"], and an input of "", the empty string, would output [].)
This question is the standard textbook case of the backtracking pattern. Backtracking means you build a candidate answer one choice at a time, then undo the most recent choice once you have explored everything that follows it. Each digit of the input contributes one choice, and the undo step lets a single growing string serve every result. The same pattern drives permutation, subset, and board-filling questions, which is why it ranks near the top of the recurring coding interview patterns. This question also appears on the Blind 75 list. Design Gurus teaches it in the Letter Combinations of a Phone Number lesson.
Hints
-
Use backtracking: Construct combinations one letter at a time. Use recursion to return to the previous digit once you exhaust the letters at a position or finish a combination.
-
Think of a tree: Picture the problem as a tree where each digit in the input expands into its possible letters, so every combination is one root-to-leaf path.
-
Iterative breadth-first search (BFS): As an alternative to recursion, use a queue to build combinations level by level, one digit at a time.
Approach 1: backtracking (recursive DFS)
Idea: A recursive depth-first search with backtracking builds every combination. Pick a letter for the first digit, then recursively solve the subproblem for the remaining digits. Then return to the first digit and try its next letter. Repeating that explores every possible letter combination:
-
Maintain a mapping of digits to letters, as given in the problem.
-
Define a recursive function that takes an index in the input string and a current combination string.
-
If the index equals the length of the input, the combination is complete, so add it to the results.
-
Otherwise, retrieve the letters for the digit at the current index and recurse for each letter. Append the letter to the current combination and move to the next index.
-
Backtracking happens as each call returns and the previous digit tries its next letter.
This approach generates a tree of combinations through DFS. Each recursive call advances to the next digit, so the depth of the recursion is at most N, the number of digits.
Complexity: In the worst case each digit maps to 4 letters, which happens for the digits 7 and 9. With N digits there are up to 4^N combinations. The time complexity is O(4^N), because every combination has to be generated. Counting the cost of building each string of length N, a more detailed analysis gives O(N * 4^N). The space complexity excluding the output list is O(N) for the recursion call stack. The output itself holds 4^N strings, which you can count as additional space usage.
Python implementation
Java implementation
Explanation: Both implementations map each digit to its corresponding letters. The recursive backtracking function builds combinations by appending one letter at a time and advancing to the next digit. In the Python code, a complete combination exists once index reaches the length of digits. In the Java code, a StringBuilder builds and rewinds the current combination string without allocating a new string per step.
Approach 2: iterative BFS with a queue
Idea: An iterative breadth-first search with a queue generates the same combinations without recursion. It builds them level by level, one digit at a time:
- Start with a queue holding the empty string
[""]as the starting combination. - For each digit in the input string, take all existing partial combinations out of the queue. Append every possible letter for that digit, and push the new combinations back into the queue.
- Continue for each digit. After the last digit, the queue holds only full-length combinations.
This approach treats the problem as a merge of several sets of letters. After the first digit, the queue holds all combinations of length 1. After the second digit it holds combinations of length 2, and so on. That is a BFS over a tree where each level adds one more letter.
Complexity: This approach generates the combinations much as the recursive solution does. It also produces 4^N combinations in the worst case, so the time complexity is O(4^N). Space complexity is O(4^N) as well, because the queue stores the partial combinations and the result list stores the finished ones.
Python implementation
In this code, for each digit we iterate over the current queue length and expand each partial combination by adding every possible letter for that digit. That bound ensures the queue holds only complete combinations of the full length at the end.
Edge cases and additional notes
-
Empty input: If
digitsis an empty string, the function returns an empty list[], since no combination can be formed. Both approaches handle this case explicitly at the start. -
Single digit: If the input has length 1, such as
"7", the output is just the list of letters for that digit. For"7"the output is["p","q","r","s"]. Either the base case in the recursion or a single pass of the iterative loop handles this naturally. -
Digits
'0'and'1': The constraints exclude0and1because they have no letter mappings. If they were allowed, you would have to decide how to handle them. The common choices are to ignore them or to treat them as having an empty set of letters, which yields no combinations. Here we assume the input holds only2through9. -
Maximum length of 4 digits: The worst case is 4 digits of all
7or9, each with 4 letters, which produces 4^4 = 256 combinations. That is small enough to generate and print. A longer input grows the count exponentially. Five digits could produce up to 1024 combinations, which is a lot of output but follows the same generation pattern. -
Order of output: The problem does not require a specific sort order. The backtracking approach generates lexicographical order by the nature of the recursion. The BFS approach generates level by level, which also happens to produce lexicographic order for this problem. Either way, all combinations appear, whatever the order.
Related problems
Generating all letter combinations for phone digits is a classic combinatorial generation problem. It resembles other questions that explore every combination or permutation, usually solved with backtracking or iterative expansion:
-
Generate Parentheses: Form all valid combinations of parentheses pairs. This is another backtracking problem where you build combinations one character at a time.
-
Permutations and combinations of sets: Generating all subsets of a set, the power set, or all permutations of a list of items.
-
Cartesian product of multiple lists: The digit-to-letter mapping gives you several lists of characters, one list per digit. The letter combinations are the Cartesian product of those lists. Questions asking for a Cartesian product, or for combinations across several categories, use similar approaches.
-
T9 predictive text on old phone keypads: T9 text input used the same digit-to-letter mappings. The difference is that T9 selects valid dictionary words rather than all combinations. Generating the letter combinations is the first stage of that idea.
-
Mnemonic phone numbers, or phonewords: Finding words or letter sequences that correspond to a phone number, such as
1-800-FLOWERS. This problem generates all possible mnemonics for a given number, with no filter against a dictionary.
For a short map of the families these questions fall into, see the common LeetCode patterns answer. The graded backtracking set, including this question, is taught in Grokking the Coding Interview.
GET YOUR FREE
Coding Questions Catalog
$99
$197
$72
