Problem statement

Given a string of digits 2-9, return all possible letter combinations the number could represent on a phone keypad (2=abc, 3=def, 4=ghi, 5=jkl, 6=mno, 7=pqrs, 8=tuv, 9=wxyz), in lexicographic order. Return an empty list for an empty input.

Example 1

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2

Input: digits = ""
Output: []

Constraints

• 0 <= digits.length <= 3
• digits[i] is a digit in ['2','9'].

Hints for Letter Combinations of a Phone Number

1. Hint 1

   Build combinations digit by digit — each digit multiplies the possibilities.

2. Hint 2

   Processing letters in keypad order yields lexicographic output naturally.

How to solve Letter Combinations of a Phone Number

Each digit multiplies the number of answers by the size of its letter group, and the groups are independent. So instead of backtracking you can just grow the answer set one digit at a time: take every combination built so far and extend it by every letter of the next digit.

Approach

1. Return an empty list immediately for an empty input — the answer is no combinations, not one empty combination.
2. Map each digit to its keypad letters.
3. Start with a single empty prefix, [""].
4. For each digit, build a fresh list: every existing prefix concatenated with every letter of that digit's group.
5. After the last digit, the list holds every combination.

Why it works

Every combination picks exactly one letter per digit, independently, so the set built after i digits is exactly the set of length-i prefixes of the final answers. Extending each prefix by each letter therefore produces every answer exactly once. Because prefixes stay in order and each digit's letters are visited in keypad order — which is alphabetical — the output comes out lexicographically sorted for free, with no sort at the end.

Complexity

• Time — O(4^n · n)
• Space — O(4^n · n)

Pitfalls

• The empty string must return []. Starting from [""] and skipping the loop would return [""], which is one combination too many.
• Iterate the letters in keypad order. Any other order still produces the right set but breaks the required lexicographic output.
• 7 and 9 have four letters, not three — an off-by-one here silently drops answers.

Reference solution

Python

from typing import List

def letterCombinations(digits: str) -> List[str]:
    if not digits:
        return []
    mapping = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
    out = [""]
    for d in digits:
        out = [prefix + ch for prefix in out for ch in mapping[d]]
    return out

Java

public static String[] letterCombinations(String digits) {
    if (digits.length() == 0) return new String[0];
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> out = new ArrayList<>();
    out.add("");
    for (char d : digits.toCharArray()) {
        String letters = map[d - '0'];
        List<String> next = new ArrayList<>();
        for (String prefix : out) {
            for (char ch : letters.toCharArray()) next.add(prefix + ch);
        }
        out = next;
    }
    return out.toArray(new String[0]);
}

C++

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return vector<string>();
    string map[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> out;
    out.push_back("");
    for (char d : digits) {
        string letters = map[d - '0'];
        vector<string> next;
        for (const string& prefix : out) {
            for (char ch : letters) next.push_back(prefix + ch);
        }
        out = next;
    }
    return out;
}

JavaScript

var letterCombinations = function(digits) {
    if (digits.length === 0) return [];
    const map = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" };
    let out = [""];
    for (const d of digits) {
        const next = [];
        for (const prefix of out) {
            for (const ch of map[d]) next.push(prefix + ch);
        }
        out = next;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium