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 in old mobile phones or landline phones). For example, 2 → “abc”, 3 → “def”, 4 → “ghi”, 5 → “jkl”, 6 → “mno”, 7 → “pqrs”, 8 → “tuv”, 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. Using this mapping, a sequence of digits can represent a sequence of letters. This problem asks us to generate all possible letter sequences that a given digit string could represent (essentially all “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 "" (empty string) would output [].)
Hints
-
Use Backtracking: Construct combinations one letter at a time, and use recursion to backtrack when you reach a dead end or complete a combination.
-
Think of a Tree: You can visualize the problem as a tree where each digit in the input expands into its possible letters, leading to branches for each combination.
-
Iterative Breadth-First Search (BFS): As an alternative to recursion, consider using a queue to build combinations level by level (digit by digit).
Approach 1: Backtracking (Recursive DFS)
Idea: We can use a recursive depth-first search (DFS) with backtracking to build all combinations. The approach is to pick a letter for the first digit, then recursively solve the subproblem for the remaining digits, and backtrack to try the next letter for the first digit, and so on. This way, we explore all possible letter combinations:
-
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, we have formed a complete combination – 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 we return from recursion and try the next letter for the previous digit.
This approach effectively generates a tree of combinations via DFS. Each recursive call progresses to the next digit, and the depth of the recursion is at most N (the number of digits).
Complexity: In the worst case each digit maps to 4 letters (for digits 7 or 9), and if there are (N) digits, there are up to (4^N) combinations. The time complexity is O((4^N)), because we have to generate all combinations. Including the cost of building each string (of length N), a more detailed analysis gives O((N \cdot 4^N)). The space complexity (excluding the output list) is O((N)) for the recursion call stack. (The output itself will contain (4^N) strings, which can be considered additional space usage.)
Python Implementation:
Java Implementation:
Explanation: In both implementations, we 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, when index reaches the length of digits, a complete combination has been formed. In the Java code, a StringBuilder is used to efficiently build and backtrack on the current combination string.
Approach 2: Iterative BFS (Queue-Based)
Idea: Another way to generate combinations is to use an iterative breadth-first search approach with a queue. The concept is to build combinations level by level (digit by digit) rather than using recursion:
- Start with a queue initialized with an empty string
[""]as the starting combination. - For each digit in the input string, take all existing partial combinations from the queue and append every possible letter for that digit, pushing these new combinations back into the queue.
- Continue this process for each digit, so that after processing all digits, the queue contains only full-length combinations.
This approach treats the problem like combining multiple sets of letters. After processing the first digit, the queue holds all combinations of length 1. After the second digit, it holds combinations of length 2, and so on. This is effectively a BFS on a tree where each level corresponds to adding one more letter.
Complexity: This approach generates the combinations in a similar manner to the recursive solution. It will also produce (4^N) combinations in the worst case, so the time complexity is O((4^N)). Space complexity is also O((4^N)) due to storing the combinations in the queue (and ultimately in the result list).
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. This ensures that by the end, the queue contains only complete combinations of the full length.
Edge Cases and Additional Notes
-
Empty Input: If
digitsis an empty string, the function returns an empty list[](no combinations can be formed). Both approaches explicitly handle this case at the start. -
Single Digit: If the input has length 1 (e.g.
"7"), the output is just the list of letters for that digit (for"7", output would be["p","q","r","s"]). The logic naturally handles this by either the base case in recursion or one pass of the iterative loop. -
Digits '0' and '1': The problem constraints exclude
0and1because they have no letter mappings. If they were allowed, one would have to decide how to handle them (commonly, they could be ignored or treated as having an empty set of letters, resulting in no combinations). In our case, we assume inputs are only2-9. -
Maximum Length (4 digits): The worst-case scenario is 4 digits of all
7or9(each having 4 letters), which produces (4^4 = 256) combinations. This is manageable to generate and output. If the input were longer, the number of combinations grows exponentially (e.g., 5 digits could produce up to 1024 combinations), which might be a lot of output but still follows the same pattern of generation. -
Order of Output: The problem does not require a specific sort order for the combinations. The backtracking approach will generate in lexicographical order by the nature of recursion, and the BFS approach will generate level-by-level (which coincidentally also results in lexicographic order for this problem). In any case, all combinations are included regardless of order.
Related Problems
Generating all letter combinations for phone digits is a classic combinatorial generation problem. It is similar in spirit to other problems that require exploring all combinations or permutations, often solved with backtracking or iterative expansion:
-
Generate Parentheses: Form all valid combinations of parentheses pairs (another backtracking problem where you build combinations character by character).
-
Permutations and Combinations of sets: e.g. generating all subsets of a set (the power set), or all permutations of a list of items.
-
Cartesian Product of Multiple Lists: The phone digit-letter mapping can be seen as multiple lists of characters (one list per digit). The letter combinations are essentially the Cartesian product of these lists. Problems asking for Cartesian product or combinations of multiple categories use similar approaches.
-
T9 Predictive Text (Old Phone Keypads): While not exactly the same task, T9 text input on old phones used the same digit-to-letter mappings. The difference is T9 tries to choose valid dictionary words rather than all combinations. However, understanding letter combinations is the first step in that concept.
-
Mnemonic Phone Numbers (Phonewords): Finding words or combinations of letters that correspond to a phone number (like
1-800-FLOWERS). Our problem is effectively generating all possible mnemonics for a given number, without filtering to actual words.
GET YOUR FREE
Coding Questions Catalog
