Letter Combinations of a Phone Number

Problem Description

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.

The digit-to-letter mapping is the same as on phone keyboards (2 maps to “abc”, 3 maps to “def”, and so on). Note that 1 does not map to any letters.

Examples

Constraints

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

One Character Per Digit, All Choices Explored

Each digit selects from a fixed set of letters. The combinations form a tree where the depth equals the number of digits and the branching factor is the number of letters for each digit (3 or 4). A complete path from root to leaf is exactly one valid combination.

Backtracking maps naturally here: for each position in the digits string, try every letter that digit can produce, append it to the current string, recurse on the next digit, then remove the last character and try the next letter.

Solution: Backtracking

import java.util.*;

class Solution {
    private static final Map<Character, String> PHONE = new HashMap<>() {{
        put('2', "abc"); put('3', "def"); put('4', "ghi");
        put('5', "jkl"); put('6', "mno"); put('7', "pqrs");
        put('8', "tuv"); put('9', "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 current, List<String> result) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        for (char letter : PHONE.get(digits.charAt(index)).toCharArray()) {
            current.append(letter);
            backtrack(digits, index + 1, current, result);
            current.deleteCharAt(current.length() - 1); // undo last letter
        }
    }
}

class Solution:
    PHONE = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }

    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        result = []

        def backtrack(index: int, current: list[str]):
            if index == len(digits):
                result.append(''.join(current))
                return

            for letter in self.PHONE[digits[index]]:
                current.append(letter)
                backtrack(index + 1, current)
                current.pop()  # undo last letter

        backtrack(0, [])
        return result

#include <vector>
#include <string>
#include <unordered_map>

class Solution {
    std::unordered_map<char, std::string> phone = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };

public:
    std::vector<std::string> letterCombinations(std::string digits) {
        std::vector<std::string> result;
        if (digits.empty()) return result;
        std::string current;
        backtrack(digits, 0, current, result);
        return result;
    }

private:
    void backtrack(const std::string& digits, int index,
                   std::string& current, std::vector<std::string>& result) {
        if (index == (int)digits.size()) {
            result.push_back(current);
            return;
        }

        for (char letter : phone[digits[index]]) {
            current.push_back(letter);
            backtrack(digits, index + 1, current, result);
            current.pop_back(); // undo last letter
        }
    }
};

Complexity Analysis:

• Time Complexity: O(4^n * n), where n is the number of digits. In the worst case (all 7s or 9s), each digit maps to 4 letters. Building each combination is O(n).
• Space Complexity: O(n) for the recursion depth and current string.

Where it breaks: the empty string case must return an empty list, not [""]. Forgetting this check and initializing result = [[""]] or similar gives wrong output for the empty input.

Common Mistakes

• Returning [""] for empty input instead of []. LeetCode’s test cases specifically check this.
• Building strings with + concatenation inside the loop. This creates a new string on every recursive call. Using a StringBuilder or a character list avoids the extra allocations.
• Hardcoding the digit mapping inline. It works, but a map or array lookup is cleaner and less error-prone (easy to mistype the letter strings).

Frequently Asked Questions

How many combinations does “999” produce? 4 * 4 * 4 = 64. Each 9 maps to 4 letters (wxyz), and combinations are independent per digit position.

Can you solve this iteratively? Yes. Start with [""], then for each digit, expand every existing combination with every letter the digit maps to, replacing the old list. Same result, no recursion stack.

What does this test in an interview? Backtracking pattern recognition and the ability to define the mapping cleanly. Interviewers look for whether you handle the empty input case and whether you can reason about the time complexity from the branching factor.

← All Problems