Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Letter Combinations of a Phone Number

MEDIUMProblemSolveExternal Links

Description

Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent. You may return the answer in any order.

This problem is based on the classic telephone keypad, where each digit maps to a set of letters:

DigitLetters
2a, b, c
3d, e, f
4g, h, i
5j, k, l
6m, n, o
7p, q, r, s
8t, u, v
9w, x, y, z

Note that the digit 1 does not map to any letters.

If the input is an empty string, return an empty list.

In simpler terms: Imagine typing a phone number on an old-style phone with letters on each button. Each digit could represent any of its letters. You need to list every possible text message that phone number could spell.

Examples

Example 1

Input: digits = "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Explanation: Digit '2' maps to letters {a, b, c} and digit '3' maps to {d, e, f}. We need every combination of one letter from the first set with one letter from the second set. There are 3 × 3 = 9 total combinations. For instance, choosing 'a' from digit 2 and 'd' from digit 3 gives "ad", choosing 'a' and 'e' gives "ae", and so on.

Example 2

Input: digits = "2"

Output: ["a", "b", "c"]

Explanation: With a single digit '2', the only combinations are the individual letters mapped to that digit: 'a', 'b', and 'c'. Each is a one-character string.

Example 3

Input: digits = ""

Output: []

Explanation: An empty input has no digits, so there are no letter combinations to generate. We return an empty list — not a list containing an empty string.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward approach is to build combinations iteratively, one digit at a time. Imagine you are writing down all possibilities on paper:

  1. Start with a blank slate — an empty partial combination.
  2. Look at the first digit. Write down each of its letters as a separate partial combination.
  3. Look at the second digit. For each partial combination you already have, extend it by appending each letter from the second digit.
  4. Repeat for every remaining digit.

This is essentially computing the Cartesian product of the letter groups, one group at a time.

Think of it like a restaurant menu with multiple courses. For the appetizer (first digit) you have 3 choices. For the main course (second digit) you also have 3 choices. The total number of unique meals is 3 × 3 = 9. You enumerate all of them by pairing every appetizer with every main course.

We maintain a running list of all partial combinations, and at each digit we expand every partial combination with every possible letter.

Step-by-Step Explanation

Let's trace through with digits = "23":

Step 1: Initialize the result list with a single empty string: result = [""].

Step 2: Process first digit '2'. Its letters are {a, b, c}. Create a new empty list for the expanded result.

Step 3: Take "" from result, append 'a' → "a". Place "a" into the new list.

Step 4: Take "" from result, append 'b' → "b". Place "b" into the new list.

Step 5: Take "" from result, append 'c' → "c". Place "c" into the new list.

Step 6: Replace old result with new list. result = ["a", "b", "c"].

Step 7: Process second digit '3'. Its letters are {d, e, f}. Create a new empty list.

Step 8: Take "a" from result, append 'd' → "ad". Place into new list.

Step 9: Take "a" from result, append 'e' → "ae". Place into new list.

Step 10: Take "a" from result, append 'f' → "af". Place into new list.

Step 11: Take "b" from result, append 'd' → "bd". Place into new list.

Step 12: Take "b" from result, append 'e' → "be". Place into new list.

Step 13: Take "b" from result, append 'f' → "bf". Place into new list.

Step 14: Take "c" from result, append 'd' → "cd". Place into new list.

Step 15: Take "c" from result, append 'e' → "ce". Place into new list.

Step 16: Take "c" from result, append 'f' → "cf". Place into new list.

Step 17: Replace old result with new list. result = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Step 18: No more digits. Return result.

The result list grew from 1 → 3 → 9 entries. At each digit, the size multiplies by the number of letters for that digit.

Iterative Combination Building: digits = "23" — The top row shows the current result list (source). The bottom row (secondary) shows the new list being built. Watch each combination appear one by one as we extend every source with every letter.

Algorithm

  1. If the input string is empty, return an empty list
  2. Create a mapping from each digit to its corresponding letters
  3. Initialize a result list containing a single empty string: [""]
  4. For each digit in the input:
    a. Look up the letters for this digit
    b. Create a new list by combining every existing partial combination with every letter
    c. Replace the result list with this new list
  5. Return the result list

Code

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        
        vector<string> phone = {"abc", "def", "ghi", "jkl", 
                                 "mno", "pqrs", "tuv", "wxyz"};
        vector<string> result = {""};
        
        for (char digit : digits) {
            string letters = phone[digit - '2'];
            vector<string> newResult;
            
            for (const string& combo : result) {
                for (char letter : letters) {
                    newResult.push_back(combo + letter);
                }
            }
            
            result = newResult;
        }
        
        return result;
    }
};
class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []
        
        phone = ["abc", "def", "ghi", "jkl",
                 "mno", "pqrs", "tuv", "wxyz"]
        
        result = [""]
        
        for digit in digits:
            letters = phone[int(digit) - 2]
            result = [combo + letter 
                      for combo in result 
                      for letter in letters]
        
        return result
class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return new ArrayList<>();
        
        String[] phone = {"abc", "def", "ghi", "jkl",
                          "mno", "pqrs", "tuv", "wxyz"};
        
        List<String> result = new ArrayList<>();
        result.add("");
        
        for (char digit : digits.toCharArray()) {
            String letters = phone[digit - '2'];
            List<String> newResult = new ArrayList<>();
            
            for (String combo : result) {
                for (char letter : letters.toCharArray()) {
                    newResult.add(combo + letter);
                }
            }
            
            result = newResult;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(4^n × n)

Where n is the number of digits. In the worst case, each digit maps to 4 letters (digits 7 and 9). So we generate up to 4^n combinations, and each combination has length n (requiring O(n) work for string concatenation). With n ≤ 4, the maximum is 4^4 = 256 combinations.

Space Complexity: O(4^n × n)

We store all generated combinations in the result list. At every intermediate step, we also maintain the previous result list until the new one is built. Each combination is a string of length up to n, so total space is O(4^n × n).

Why This Approach Is Not Efficient

The iterative approach works perfectly for this problem's small constraints (n ≤ 4), but it has a structural drawback: it stores all intermediate partial combinations in memory at every step.

During the transition from one digit to the next, both the old and new result lists exist simultaneously. For the first digit, we have up to 4 partial combinations. For the second, up to 16 (4 old × 4 new). By the time we reach the fourth digit, we briefly hold both the third-stage list (up to 64 entries) and the final list (up to 256 entries) in memory.

More importantly, this approach doesn't generalize well to other combinatorial problems. In interviews, problems like "generate all permutations", "generate all subsets", or "solve N-Queens" follow a common backtracking pattern. The iterative Cartesian-product style doesn't transfer to those problems.

A backtracking (DFS) approach builds one combination at a time, using the call stack to track progress. It only ever holds one partial combination of length n in memory at once (plus the final result list). It also naturally teaches the recursive decision-tree paradigm that is fundamental to combinatorial search problems.

Optimal Approach - Backtracking

Intuition

Backtracking is a systematic way to explore all possibilities by making a choice, exploring what follows, and then undoing ("backtracking") the choice to try the next option.

Imagine you are standing at a crossroads with multiple paths. You pick one path and walk down it. At the next crossroads, you again pick a path. You keep going until you either reach a dead end or your destination. If you reach the destination, great — record the path. Then go back to the last crossroads and try a different path.

For this problem:

  • Each digit is a "crossroads" with 3 or 4 paths (its letters)
  • A "path" is the sequence of letters chosen so far
  • When the path length equals the number of digits, we've reached the "destination" — record this combination
  • Then backtrack: remove the last letter and try the next one

This creates a decision tree where each level corresponds to one digit, and each branch corresponds to choosing a specific letter. The leaves of this tree are all the valid combinations.

For digits = "23", the tree looks like:

          root
        / | \
       a  b  c       (digit '2')
      /|\ /|\ /|\
     d e f d e f d e f  (digit '3')

Each root-to-leaf path is one combination: ad, ae, af, bd, be, bf, cd, ce, cf.

Step-by-Step Explanation

Let's trace through with digits = "23":

Step 1: Start backtrack with path = "", index = 0.

Step 2: Digit at index 0 is '2', letters = {a, b, c}. Choose 'a'. path = "a", index = 1.

Step 3: Digit at index 1 is '3', letters = {d, e, f}. Choose 'd'. path = "ad", index = 2.

Step 4: index (2) == len(digits) (2). Path is complete! Add "ad" to results.

Step 5: Backtrack: remove 'd' from path. path = "a".

Step 6: Try next letter 'e'. path = "ae", index = 2. Complete! Add "ae".

Step 7: Backtrack: remove 'e'. path = "a".

Step 8: Try next letter 'f'. path = "af", index = 2. Complete! Add "af".

Step 9: Backtrack: remove 'f'. path = "a". No more letters for digit '3'. Backtrack further: remove 'a'. path = "".

Step 10: Try next letter 'b' for digit '2'. path = "b", index = 1.

Step 11: Choose 'd' for digit '3'. path = "bd". Complete! Add "bd".

Step 12: Backtrack, try 'e'. path = "be". Complete! Add "be".

Step 13: Backtrack, try 'f'. path = "bf". Complete! Add "bf".

Step 14: Backtrack from 'b' entirely. path = "". Try 'c' for digit '2'. path = "c", index = 1.

Step 15: Choose 'd'. path = "cd". Complete! Add "cd".

Step 16: Backtrack, try 'e'. path = "ce". Complete! Add "ce".

Step 17: Backtrack, try 'f'. path = "cf". Complete! Add "cf".

Step 18: Backtrack from 'c'. path = "". No more letters for digit '2'. All paths explored.

Step 19: Return result = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Backtracking Decision Tree: digits = "23" — Watch how backtracking explores the decision tree depth-first. Each node represents a recursive call. The tree grows as choices are made, and nodes are resolved as combinations are collected or branches are exhausted.

Algorithm

  1. If the input string is empty, return an empty list
  2. Create a mapping from each digit to its corresponding letters
  3. Define a recursive function backtrack(path, index):
    a. If index equals len(digits), the path is complete → add it to results and return
    b. Get the letters for digits[index]
    c. For each letter:
    • Append the letter to the path
    • Recursively call backtrack(path, index + 1)
    • Remove the letter from the path (backtrack)
  4. Call backtrack with an empty path and index 0
  5. Return the results list

Code

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        
        vector<string> phone = {"abc", "def", "ghi", "jkl",
                                 "mno", "pqrs", "tuv", "wxyz"};
        vector<string> result;
        string path;
        
        backtrack(digits, phone, 0, path, result);
        return result;
    }
    
private:
    void backtrack(const string& digits, const vector<string>& phone,
                   int index, string& path, vector<string>& result) {
        if (index == digits.size()) {
            result.push_back(path);
            return;
        }
        
        string letters = phone[digits[index] - '2'];
        for (char letter : letters) {
            path.push_back(letter);
            backtrack(digits, phone, index + 1, path, result);
            path.pop_back();  // Backtrack
        }
    }
};
class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []
        
        phone = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
                 "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        
        result = []
        
        def backtrack(index: int, path: list[str]) -> None:
            if index == len(digits):
                result.append("".join(path))
                return
            
            for letter in phone[digits[index]]:
                path.append(letter)
                backtrack(index + 1, path)
                path.pop()  # Backtrack
        
        backtrack(0, [])
        return result
class Solution {
    private static final String[] PHONE = {
        "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };
    
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;
        
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }
    
    private void backtrack(String digits, int index,
                           StringBuilder path, List<String> result) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }
        
        String letters = PHONE[digits.charAt(index) - '2'];
        for (char letter : letters.toCharArray()) {
            path.append(letter);
            backtrack(digits, index + 1, path, result);
            path.deleteCharAt(path.length() - 1);  // Backtrack
        }
    }
}

Complexity Analysis

Time Complexity: O(4^n × n)

Where n is the number of digits. In the worst case (all digits are 7 or 9), each digit branches into 4 letters. The recursion tree has 4^n leaf nodes, and at each leaf we copy a string of length n into the result. Total work: O(4^n × n).

The time complexity is the same as the iterative approach — we must generate all combinations regardless of method.

Space Complexity: O(n) auxiliary space (excluding the output)

The recursion stack depth is at most n (one level per digit). The path variable uses at most n characters. The result list holds all 4^n combinations (output space), but if we exclude the required output, the working space is just O(n).

This is an improvement over the iterative approach, which needed O(4^n × n) space for intermediate lists during construction. The backtracking approach only ever holds one partial path on the stack at a time, making it more memory-efficient during the generation process.