Log inSign up
mediumLeetCodeNot Started

Letter Combinations of a Phone Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

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.

* 2: "abc" * 3: "def" * 4: "ghi" * 5: "jkl" * 6: "mno" * 7: "pqrs" * 8: "tuv" * 9: "wxyz"

Example 1 · 2-Digit Input '23':

Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explanation: 2 maps to abc, 3 maps to def. Cartesian product yields 3 * 3 = 9 combinations.

Example 2 · Empty Digits:

Input: digits = ""
Output: []
Explanation: An empty string produces an empty array of combinations.

Example 3 · Single Digit '2':

Input: digits = "2"
Output: ["a", "b", "c"]
Explanation: Single digit produces its corresponding characters.

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range [2, 9].

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master multi-way tree exploration across variable-size character sets (3 or 4 choices per node).
  • Understand Cartesian product generation using both recursion and iterative FIFO queue expansion.
  • Correctly handle empty input edge cases.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generate all possible string combinations from sequential digit mappings
  • Phone keypad mapping constraints
  • Combinations formed by picking exactly 1 letter from each group

Algorithmic Decision Tree:

  • Map digits 2-9 in a static lookup array.
  • Handle empty string digits == '' as an explicit base case returning [].
  • Backtrack with idx: for each char in map[digits[idx]], push char, recurse idx + 1, and pop char.

Connected Patterns:

CombinationsPermutationsGenerate Parentheses

1. Iterative Nested Loops (Hardcoded for length <= 4)

Intuition

Extract character sets for each digit. Based on digits.length, run 1, 2, 3, or 4 nested loops combining characters.

When to apply: Simple conceptual approach when constraint is strictly fixed at 4.

Algorithm

  1. If digits.isEmpty(), return [].
  2. Based on length, execute 1 to 4 nested loops over mapped character sets.
  3. Append combined string to result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<string> letterCombinations(string digits) {
10 if (digits.empty()) return {};
11 vector<string> map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
12 vector<string> result = {""};
13
14 for (char d : digits) {
15 string letters = map[d - '0'];
16 vector<string> temp;
17 for (const string& prefix : result) {
18 for (char c : letters) {
19 temp.push_back(prefix + c);
20 }
21 }
22 result = move(temp);
23 }
24 return result;
25 }
26};
27
28int main() {
29 Solution sol;
30 auto res = sol.letterCombinations("23");
31 for (const string& s : res) cout << s << " ";
32 cout << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(4^N * N) — Generates all combinations directly.
  • Space complexity: O(1) — Uses constant auxiliary space beyond result.

2. BFS / Queue Expansion Approach

Intuition

Initialize queue with an empty string ''. For each digit, pop all elements currently of length d, append each mapped letter, and push back onto the queue. When all digits are processed, the queue contains all complete combinations.

When to apply: When avoiding recursive call stacks or streaming combinations iteratively.

Algorithm

  1. Initialize FIFO queue with [''].
  2. Loop through each character d in digits:
  3. - While queue head length matches current iteration:
  4. - Pop prefix from queue.
  5. - For each c in map[d]: push prefix + c into queue.
  6. Return queue contents.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <queue>
5
6using namespace std;
7
8class Solution {
9public:
10 vector<string> letterCombinations(string digits) {
11 if (digits.empty()) return {};
12 vector<string> map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
13 queue<string> q;
14 q.push("");
15
16 for (int i = 0; i < digits.length(); i++) {
17 string letters = map[digits[i] - '0'];
18 int sz = q.size();
19 for (int s = 0; s < sz; s++) {
20 string prefix = q.front();
21 q.pop();
22 for (char c : letters) {
23 q.push(prefix + c);
24 }
25 }
26 }
27
28 vector<string> result;
29 while (!q.empty()) {
30 result.push_back(q.front());
31 q.pop();
32 }
33 return result;
34 }
35};
36
37int main() {
38 Solution sol;
39 auto res = sol.letterCombinations("23");
40 for (const string& s : res) cout << s << " ";
41 cout << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(4^N * N) — Queue stores intermediate string combinations.
  • Space complexity: O(4^N * N) — Maximum queue size equals total combinations count.

3. Recursive DFS Backtracking with String Path (Optimal)

Intuition

Define backtrack(idx, current). When idx == digits.length, append copy of current to result. For each character in map[digits[idx]], push character to path, recurse idx + 1, and pop character upon return.

When to apply: The standard gold-standard recursive interview solution.

Algorithm

  1. If digits.isEmpty(), return [].
  2. Define backtrack(idx, current):
  3. - If idx == digits.length, add current to result and return.
  4. - Look up letters = map[digits[idx]].
  5. - For each c in letters:
  6. - Push c to current.
  7. - Recurse backtrack(idx + 1, current).
  8. - Pop c from current.
  9. Start backtrack(0, '').

Keypad Combinations Tree Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Root at index 0: digits[0] = '2', choices are {'a', 'b', 'c'}
Visual state
Values and pointers at this exact step
tree
Root
digits: '23', idx: 0

Node order shown; add connections to display explicit tree edges.

Variables at this step
idx
0
current
Why this step matters

Root at index 0: digits[0] = '2', choices are {a, b, c}.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 vector<string> map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
9
10 void backtrack(int idx, const string& digits, string& current, vector<string>& result) {
11 if (idx == digits.length()) {
12 result.push_back(current);
13 return;
14 }
15
16 string letters = map[digits[idx] - '0'];
17 for (char c : letters) {
18 current.push_back(c);
19 backtrack(idx + 1, digits, current, result);
20 current.pop_back(); // backtrack
21 }
22 }
23
24public:
25 vector<string> letterCombinations(string digits) {
26 if (digits.empty()) return {};
27 vector<string> result;
28 string current;
29 backtrack(0, digits, current, result);
30 return result;
31 }
32};
33
34int main() {
35 Solution sol;
36 auto res = sol.letterCombinations("23");
37 for (const string& s : res) cout << s << " ";
38 cout << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(4^N * N) — There are up to 4N combinations, each of length N copied to result.
  • Space complexity: O(N) — Recursion depth is strictly bounded by digits.length <= 4.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative Nested LoopsO(4^N * N)O(1)Nested loop string expansion per digit.Intermediate array allocation
2.BFS / Queue ExpansionO(4^N * N)O(4^N * N)FIFO queue level-by-level prefix expansion.Queue memory footprint
3.Recursive DFS Backtracking with String PathOptimalO(4^N * N)O(N)Depth-first recursive tree traversal with single mutable buffer.Output generation count

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning [''] instead of [] for an empty input string ''.

Pitfall 2:

Hardcoding 0-based array index without subtracting '0' or adjusting for unused digits 0 and 1.

Crucial Edge Cases to Validate:

  • Empty String: digits = '' -> returns [].
  • Single Digit: digits = 7 -> returns [p, q, r, s].
  • Digits with 4 Letters: 7 (pqrs) and 9 (wxyz) have 4 branching choices instead of 3.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Check for empty input first (if (digits.empty()) return {};).
  2. Explain why DFS requires only O(N) memory compared to BFS requiring O(4N) queue memory.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the maximum number of combinations returned by this problem given the constraint 0 <= digits.length <= 4?

2.What must be returned when digits = ''?

Back to DSA Sheet