Letter Combinations of
a Phone Number

The Phone Keypad Mapping

Each digit on a phone maps to a set of letters. Given a string of digits, we must return every possible letter combination those digits could represent.

Brute Force — Why Simple Loops Fail

For two digits, we could write a double-nested loop. For three digits, a triple-nested loop. But the number of digits is variable (0 to 4), so we cannot hardcode the nesting depth.

// For digits = "23" — works fine with 2 loops
for (char c1 : "abc".toCharArray())
    for (char c2 : "def".toCharArray())
        result.add("" + c1 + c2);

// For digits = "234" — need 3 loops
for (char c1 : "abc".toCharArray())
    for (char c2 : "def".toCharArray())
        for (char c3 : "ghi".toCharArray())
            result.add("" + c1 + c2 + c3);

// For digits = "2345" — need 4 loops...
// How many loops for n digits? We can't know at compile time!

The Core Insight — Backtracking

We build each combination one character at a time. At each digit position, we try every letter that digit maps to, recurse deeper for the next digit, then undo our choice (backtrack) before trying the next letter.

This creates a decision tree where each level corresponds to a digit, and each branch to a letter choice. For digits = "23":

Algorithm Walkthrough

Let's trace every recursive call for digits = "23". Watch the path build up and get undone:

Edge Cases

The problem has a few important boundary conditions to handle:

Full Annotated Code

class Solution {

    // Index 0 and 1 are empty — digits 0 and 1 have no letters
    private static final String[] MAPPING = {
        "", "", "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        // Guard: empty input returns empty list (not [""])
        if (digits.isEmpty()) return result;

        // Start backtracking from digit index 0
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void backtrack(String digits, int index,
                           StringBuilder path, List<String> result) {

        // Base case: built a complete combination
        if (index == digits.length()) {
            result.add(path.toString());   // snapshot the path
            return;
        }

        // Get letters for current digit
        String letters = MAPPING[digits.charAt(index) - '0'];

        for (char c : letters.toCharArray()) {
            path.append(c);                  // 1. Choose
            backtrack(digits, index + 1,     // 2. Explore
                      path, result);
            path.deleteCharAt(                // 3. Un-choose
                path.length() - 1);
        }
    }
}

Interactive Demo

Enter digits and watch the backtracking tree build up step by step. Each step shows the algorithm choosing a letter, exploring deeper, or backtracking.

Complexity Analysis