Letter Combinations of a Phone Number

MEDIUM✓ CHIP-TIMEDLC #17 — FULL STATEMENT ↗

The drill: Old telephone keypads map digits 2 through 9 to a few letters each. Given a string of such digits, produce every string you could spell by choosing one letter per digit, in order.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string of digits 2 through 9 arrives, each digit standing for a handful of letters the way an old telephone keypad grouped them. The task is to produce every string spellable by picking one letter from each digit, in the digits' original order.

Every output string is exactly as long as the input digit string — one letter contributed per digit, no digit skipped or reused — and every combination the keypad allows should show up exactly once.

An empty digit string is its own edge case: with no digits to draw letters from, the honest answer is no combinations at all.

EX 01

digits = ""

→ []

NO DIGITS, NOTHING TO SPELL

EX 02

digits = "2"

→ ["a", "b", "c"]

MINIMUM SIZE, THREE-LETTER DIGIT

EX 03

digits = "7"

→ ["p", "q", "r", "s"]

SINGLE FOUR-LETTER DIGIT

digits are limited to 2 through 9; 0 and 1 don't appear
the digit string is short, generally four or fewer characters
each digit maps to three or four letters, per the classic keypad layout
an empty input produces an empty result

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Each digit multiplies the possibilities of the ones before it — three digits worth three letters each is a cartesian product wearing a phone's disguise. How would you grow the answer one digit at a time?

HINT 2 THE STRUCTURE

Map each digit to its letters, then extend every existing prefix by each letter of the next digit. The same idea also works one character at a time with a single shared buffer instead of rebuilding whole strings.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack over positions: append the next digit's letter to a shared path, recurse to the next digit, then pop the letter off before trying the next one — the buffer becomes every full-length combination in turn.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE KEYPAD BUFFERPATTERN · BACKTRACKING DFSdigits = "23"

STEP 1

Digits '2' then '3'. Each digit contributes one letter; a shared buffer grows and shrinks as we try every combination.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/letter-combinations-of-a-phone-number.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def letterCombinations(self, 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",
        }
        result = []
        path = []

        def backtrack(i: int) -> None:
            if i == len(digits):
                result.append("".join(path))
                return
            for letter in mapping[digits[i]]:
                path.append(letter)
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result

TIME O(4^N · N)SPACE O(N)PYTHON · RACE PACE · 22 LN

class Solution:
    def letterCombinations(self, 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",
        }
        combos = [""]
        for d in digits:
            combos = [prefix + letter for prefix in combos for letter in mapping[d]]
        return combos

TIME O(4^N · N)SPACE O(4^N · N)PYTHON · TRAINING PACE · 12 LN

class Solution {
    private static final String[] MAPPING = {"", "", "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 i, StringBuilder path, List<String> result) {
        if (i == digits.length()) {
            result.add(path.toString());
            return;
        }
        String letters = MAPPING[digits.charAt(i) - '0'];
        for (char letter : letters.toCharArray()) {
            path.append(letter);
            backtrack(digits, i + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

TIME O(4^N · N)SPACE O(N)JAVA · RACE PACE · 25 LN

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combos = new ArrayList<>();
        if (digits.isEmpty()) {
            return combos;
        }
        String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        combos.add("");
        for (char d : digits.toCharArray()) {
            String letters = mapping[d - '0'];
            List<String> next = new ArrayList<>();
            for (String prefix : combos) {
                for (char letter : letters.toCharArray()) {
                    next.add(prefix + letter);
                }
            }
            combos = next;
        }
        return combos;
    }
}

TIME O(4^N · N)SPACE O(4^N · N)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED