Letter Combinations of a Phone Number

Problem

On an old phone keypad each digit from 2 to 9 maps to a group of letters: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz (1 and 0 map to nothing). Given a string digits containing only characters 2–9, return every string that can be formed by picking one letter for each digit, in the digits’ order. Return them in any order. If digits is empty, return an empty list.

Examples

• digits = "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"] — 3 letters for 2 × 3 letters for 3 = 9 strings.
• digits = "" → [] — no digits means no combinations (not [""]).
• digits = "7" → ["p","q","r","s"] — a single 4-letter digit.

Constraints

• 0 <= len(digits) <= 4
• digits[i] is a character in '2'..'9'

With at most 4 digits and at most 4 letters per digit, the output holds at most 4^4 = 256 strings — the output size is the running time, so every correct algorithm is asymptotically optimal; the exercise is structuring the generation cleanly.

Think about it first

TL;DR

DFS backtracking over one letter per digit — O(4^n · n) time, O(n) space beyond the output (n = number of digits).

Approach 1 — Brute force: iterative prefix expansion

There is no meaningfully worse brute force here — the output has up to 4^n strings, so every correct algorithm pays at least O(4^n · n) just to write it down. The naive-but-fine starting point is breadth-first expansion: keep the list of all prefixes built so far, and for each new digit replace the list with every prefix extended by every letter of that digit.

from typing import List

KEYPAD = {
    "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
    "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
}


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        prefixes = [""]
        for d in digits:
            letters = KEYPAD[d]
            prefixes = [p + ch for p in prefixes for ch in letters]
        return prefixes

Walkthrough on digits = "23":

Complexity: O(4^n · n) time (each of ≤ 4^n final strings is built through n concatenations), O(4^n · n) working space since every intermediate generation is materialized. The constraints don’t kill it — nothing can beat output size — but it holds all prefixes in memory at once, and the interview point of this problem is the DFS version below.

Approach 2 — Backtracking (DFS on the digit index)

The insight: the answers are the leaves of a tree whose level i branches once per letter of digits[i] — so a depth-first traversal that carries the current path visits every leaf while storing only one partial string at a time. This is backtracking: extend the partial solution by one choice, recurse, then undo the choice and try the next.

from typing import List

KEYPAD = {
    "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
    "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
}


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        result: List[str] = []
        path: List[str] = []

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

        backtrack(0)
        return result

Walkthrough on digits = "23":

• i=0, pick a → i=1, pick d → i=2 → record "ad", pop d; pick e → "ae", pop; pick f → "af", pop; pop a.
• Pick b → same inner loop → "bd", "be", "bf".
• Pick c → "cd", "ce", "cf".

Nine leaves, visited in dictionary order, with never more than 2 characters of working path in memory.

Complexity: O(4^n · n) time (4 is the largest letter group, the join costs n per leaf); O(n) extra space for path and recursion — the advantage over Approach 1’s O(4^n · n) working set.

Approach 3 — Library cross product

The insight: “one letter per digit, all ways” is literally the Cartesian product of the letter groups — Python ships it as itertools.product, which internally does the same odometer-style enumeration. Worth writing in real code; in an interview, mention it and then hand-roll Approach 2.

from itertools import product
from typing import List

KEYPAD = {
    "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
    "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
}


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        groups = [KEYPAD[d] for d in digits]
        return ["".join(combo) for combo in product(*groups)]

Walkthrough on digits = "7": groups = ["pqrs"], and the product of a single group is its letters one at a time → ["p","q","r","s"].

Complexity: O(4^n · n) time, O(n) space beyond the output (product yields tuples lazily).

Common pitfalls

• Returning [""] instead of [] for empty input — the empty product technically has one element, but the problem wants an empty list; guard if not digits first.
• Building the path by string concatenation into the recursive call (backtrack(i + 1, s + ch)) is fine at n ≤ 4 but copies the whole prefix at every level — the append/pop list idiom is the scalable habit.
• Forgetting that 7 and 9 map to four letters — hardcoding 3 breaks half the keypad.
• Mapping 1 or 0 to letters — the constraints exclude them, but a defensive KEYPAD lookup would raise a KeyError rather than silently produce wrong output, which is what you want.

Pattern takeaway

This is backtracking with zero pruning — a pure enumeration where the recursion tree is the answer set. Recognize the shape: when each position has an independent menu of options and you need every full selection, DFS with append/recurse/pop generates the cross product in O(depth) working memory. The same skeleton reappears with pruning bolted on in constraint problems (N-Queens, Sudoku), so it’s worth being able to write this version without thinking.