Letter Combinations of a Phone Number

Problem in plain words

Old phone keypads map each digit from 2 to 9 to a few letters (2 is abc, 7 is pqrs, 9 is wxyz, and so on). Given a string of such digits, list every word you could spell by choosing one letter for each digit, in order. If the input is empty, return an empty list.

For example, "34" maps to def and ghi, giving nine strings: dg, dh, di, eg, eh, ei, fg, fh, fi.

Intuition

Think of a decision tree. The first level chooses a letter for the first digit, the second level chooses a letter for the second digit, and so on. Every path from the root to a leaf is one answer. Walking this tree depth-first while keeping a single growing string is exactly backtracking: append a letter, explore deeper, then remove the letter and try the next one. It is the same choose / explore / un-choose rhythm used in the N-Queens lesson, just without any pruning because every path is valid.

Approach

1. If digits is empty, return an empty list right away.
2. Store the keypad as an array indexed by digit: index 2 holds abc, index 9 holds wxyz.
3. Write backtrack(index, path). If index == digits.length, add path to the result and return.
4. Otherwise, for each letter mapped to digits[index], append it to path, call backtrack(index + 1, path), and then remove the last character.
5. Start with backtrack(0, empty) and return the collected list.

Dry run

Input: "29", where 2 is abc and 9 is wxyz.

1. Choose a for digit 2. Then try each letter of 9: record aw, ax, ay, az. Remove a.
2. Choose b: record bw, bx, by, bz. Remove b.
3. Choose c: record cw, cx, cy, cz.
4. Total: 3 * 4 = 12 strings, produced in lexicographic order because the letters are tried in order.

Java solution

class Solution {
    private static final String[] KEYS = {
        "", "", "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 = KEYS[digits.charAt(index) - '0'];
        for (char ch : letters.toCharArray()) {
            path.append(ch);                       // choose
            backtrack(digits, index + 1, path, result);  // explore
            path.deleteCharAt(path.length() - 1);  // un-choose
        }
    }
}

Python solution

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        keys = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        result = []
        path = []

        def backtrack(index):
            if index == len(digits):
                result.append("".join(path))
                return
            for ch in keys[int(digits[index])]:
                path.append(ch)        # choose
                backtrack(index + 1)   # explore
                path.pop()             # un-choose

        backtrack(0)
        return result

Complexity

Edge cases and common mistakes

• Empty input: the expected answer is [], not [""]. Without the early return, the base case would add one empty string.
• Digits 7 and 9 have four letters: hard-coding three letters per key silently drops answers.
• Forgetting to un-choose: if you append without removing, the path keeps growing and later answers are corrupted.
• String concatenation in Java: passing path + ch works but creates many temporary strings; a single StringBuilder is cleaner.