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'].The key idea behind #17 Letter Combinations of a Phone Number is to simulate the mapping of digits to letters on a traditional phone keypad. Each digit from 2-9 corresponds to a set of characters. The task is to generate all possible letter combinations that the input digit string could represent.
A common and efficient strategy is backtracking. First, store the digit-to-letter mapping in a hash table or array. Then recursively build combinations by selecting one letter for the current digit and moving to the next digit. When the length of the current combination matches the input length, add it to the result list.
This approach systematically explores every possible combination. Because each digit can map to up to 4 letters, the number of combinations grows exponentially. The time complexity is approximately O(4^n * n), where n is the number of digits, while the recursion stack contributes O(n) auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with digit-to-letter mapping | O(4^n * n) | O(n) |
| BFS / Iterative combination building | O(4^n * n) | O(4^n) |
NeetCode
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.
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.
1var letterCombinations = function(digits) {
2 if (digits.length === 0) return [];
3
This JavaScript solution follows the recursive backtracking paradigm similarly employed by the other language solutions. The digits are processed to find respective character mappings, and recursive depth-first search via the helper backtrack function churns through all possible outcomes.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is frequently asked in technical interviews at companies like Google, Amazon, and Meta. It tests understanding of recursion, backtracking, and combinatorial generation using strings.
Yes, it can also be solved using an iterative BFS-style approach. In this method, you build combinations level by level using a queue or list, expanding each partial string with letters mapped to the next digit.
A hash table or array is typically used to store the mapping between digits and their corresponding letters on a phone keypad. This allows constant-time access when expanding combinations during recursion or iteration.
The optimal approach uses backtracking. By mapping each digit to its corresponding letters and recursively building combinations, you can systematically generate all possible strings. This approach is efficient and commonly expected in coding interviews.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<string> LetterCombinations(string digits) {
6 List<string> combinations = new List<string>();
7 if (digits.Length == 0) return combinations;
8 string[] phoneMap = new string[] {
9 "", "", "abc", "def",
10 "ghi", "jkl", "mno",
11 "pqrs", "tuv", "wxyz"
12 };
13 Queue<string> queue = new Queue<string>();
14 queue.Enqueue("");
15 foreach (char digit in digits.ToCharArray()) {
16 int levelSize = queue.Count;
17 for (int i = 0; i < levelSize; i++) {
18 string prevCombination = queue.Dequeue();
19 foreach (char letter in phoneMap[digit - '0'].ToCharArray()) {
20 queue.Enqueue(prevCombination + letter);
21 }
22 }
23 }
24 while (queue.Count != 0) {
25 combinations.Add(queue.Dequeue());
26 }
27 return combinations;
28 }
29
30 public static void Main(string[] args) {
31 Solution sol = new Solution();
32 var result = sol.LetterCombinations("23");
33 foreach (var combination in result) {
34 Console.WriteLine(combination);
35 }
36 }
37}The C# version integrates queue mechanics to navigate valid letter combinations by adding and removing segments iteratively. Its result is built through background enqueuing, revealing comprehensive digit pairings post-traversal.