17. Letter Combinations of a Phone Number

Map each digit to its phone-keypad letters, then DFS one digit per level — appending every mapped letter and recording the path when it reaches full length. Classic backtrackingshape: choose, recurse, and the call-stack unwinds the "undo" automatically because strings are immutable.

● MediumBacktrackingDFSRecursionTypeScript

PROBLEM What we're solving

Given a string of digits 2–9, return every letter string you can spell using the phone-keypad mapping. Digits map like a T9 keyboard: 2 → abc, 3 → def, …, 9 → wxyz. For example, digits = "23" produces ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] — all 9 combinations (3 letters × 3 letters). Empty input returns [].

KEY IDEA One digit per DFS depth, one letter per branch

Insight → treat the digit string as a sequence of decisions. At depth idx you pick one of the letters mapped to digits[idx] and recurse to depth idx + 1. When idxequals the digit count, the accumulated path is one complete combination. No explicit "undo" step is needed because path + letter creates a new string — the call stack itself is the backtrack.

RECIPE Build the digit→letters map, then DFS

0 · Guard empty input. Return [] immediately if digits is empty — there are no combinations, not one empty string.
1 · Build the map. Hard-code Record<string, string[]> for digits 2–9. Note 7 and 9 each have four letters.
2 · DFS(idx, path). If idx === digits.length, push path to results and return (base case).
3 · Branch. For each letter in map[digits[idx]], recurse with dfs(idx + 1, path + letter). String concatenation creates a fresh string, so no manual undo is needed.
4 · Collect. Call dfs(0, '') and return results.

Classic confusion → returning [""] instead of [] for empty input. The problem explicitly says return an empty list — not a list containing one empty string. Always guard if (!digits.length) return [] first.

COST Complexity & alternatives

Iterative product (no recursion)

O(4ⁿ · n)

Start with [], for each digit append all its letters to every existing string. Same result, harder to read.

DFS / backtracking

O(4ⁿ · n)

In the worst case (all 4-letter digits like 7, 9) you produce 4ⁿ strings, each of length n. DFS is the cleaner expression of the same work.

Both approaches are output-bound — the work you do is proportional to the result you must return, so there is no better algorithm, only cleaner code.

Pattern transfer → this is the textbook backtracking template. The same shape solves Combinations (LC 77), Permutations (LC 46), Combination Sum (LC 39), and Subsets (LC 78) — only the branching factor and pruning condition change.

RUN IT DFS one digit per depth, append each mapped letter

digits =

step 0 / 22

STARTBegin DFS on digits 23. Each level picks one letter for one digit.

1▶function letterCombinations(digits: string): string[] {
2  if (!digits.length) return [];
3 
4  const map: Record<string, string[]> = {
5    '2': ['a','b','c'], '3': ['d','e','f'],
6    '4': ['g','h','i'], '5': ['j','k','l'],
7    '6': ['m','n','o'], '7': ['p','q','r','s'],
8    '8': ['t','u','v'], '9': ['w','x','y','z'],
9  };
10 
11▶  const results: string[] = [];
12 
13  function dfs(idx: number, path: string): void {
14    if (idx === digits.length) {
15      results.push(path);
16      return;
17    }
18    for (const letter of map[digits[idx]]) {
19      dfs(idx + 1, path + letter);  // recurse one digit deeper
20    }
21  }
22 
23▶  dfs(0, '');
24  return results;
25}

digits2031

State

idx

"2"

digit

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

letters

—

letter

path

depth

[]

results

current digit / letter being exploreddigits already committedcombination recorded

slowfast

TYPESCRIPT The solution, annotated

letterCombinations.ts
function letterCombinations(digits: string): string[] {
  if (!digits.length) return [];

  const map: Record<string, string[]> = {
    '2': ['a','b','c'], '3': ['d','e','f'],
    '4': ['g','h','i'], '5': ['j','k','l'],
    '6': ['m','n','o'], '7': ['p','q','r','s'],
    '8': ['t','u','v'], '9': ['w','x','y','z'],
  };

  const results: string[] = [];

  function dfs(idx: number, path: string): void {
    if (idx === digits.length) {
      results.push(path);
      return;
    }
    for (const letter of map[digits[idx]]) {
      dfs(idx + 1, path + letter);  // recurse one digit deeper
    }
  }

  dfs(0, '');
  return results;
}

Reading it block by block

Line 2 — guard empty input. An empty digits string produces zero combinations — return [], not [""]. This edge case trips many implementations that forget it.

Lines 4–10 — digit-to-letters map. A plain Record<string, string[]> is the clearest way to encode T9. Note that 7 maps to four letters (pqrs) and so does 9 (wxyz) — easy to miss when hard-coding.

Lines 14–20 — DFS function. idx tracks which digit we are deciding for; path accumulates the letters chosen so far. The base case (idx === digits.length) records a complete combination.

Lines 18–20 — branching. For each letter the current digit maps to, we call dfs(idx + 1, path + letter). Because strings are immutable, path + lettercreates a new string — no explicit "undo" step is needed. The call-stack unwinds the choice automatically.

Lines 23–24 — kick off and return. A single dfs(0, '') seeds the recursion and fills results. Return it.

Complexity → O(4ⁿ · n) time — in the worst case every digit maps to 4 letters (e.g. all nines), giving 4ⁿ leaves each requiring O(n) to copy into the results array. Space is O(n) for the call stack (depth = number of digits) plus O(4ⁿ · n) for the output list itself. There is no way to beat output-bound work.

INTERVIEWFollow-ups they'll ask

"What about digits 0 and 1?" The original problem guarantees 2–9. If they can appear, skip or treat them as empty mappings — a guard in the branch loop covers it cleanly.
"Return in lexicographic order?" DFS naturally produces lexicographic output if the letters in the map are in alphabetical order (they already are). No extra sort needed.
"Iterative version?" Initialize a list with one empty string. For each digit, expand every existing string by all its mapped letters. Same O(4ⁿ · n) cost, but the recursive version is far easier to read.
"How does this generalize to Combination Sum / Permutations?" The skeleton is identical — the only change is the branching condition (digits here; candidate list with pruning for Combination Sum; remaining elements for Permutations).
"What if we want only combinations of length k?" Add a pruning condition: if path.length + (digits.length - idx) < k, prune. This is the standard "early exit" optimization in backtracking.

MNEMONIC The one-liner

"DFS: go one digit deep, try each letter, the call-stack unwinds for free."

TRIGGERS When you see _ → reach for _

"all combinations of …"	backtracking DFS skeleton
phone pad / T9 digit mapping	digit→letters map + DFS
each character has multiple choices	branch per choice, recurse to next position
enumerate every valid string / subset / permutation	backtracking template

SKELETON The reusable shape

skeleton.ts
const map: Record<string, string[]> = { '2':['a','b','c'], /* ... */ };
const results: string[] = [];

function dfs(idx: number, path: string): void {
  if (idx === digits.length) {
    results.push(path);
    return;
  }
  for (const letter of map[digits[idx]]) {
    dfs(idx + 1, path + letter);
  }
}

dfs(0, '');
return results;

FLASHCARDS Tap to flip

What is the base case for the DFS?

When idx === digits.length — the path is complete, push it to results.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What does letterCombinations("23") return?

QUESTION 02

What should letterCombinations("") return?

QUESTION 03

What is the time complexity for n digits (worst case)?

QUESTION 04

Why does the recursive solution need no explicit "undo" (backtrack) step?

QUESTION 05

If you replace string concatenation with a mutable array (push/pop), what must you add?

QUESTION 06

Which digits map to 4 letters on the T9 keypad?

QUESTION 07

How many combinations are produced for digits = "79"?

QUESTION 08

#17 · Letter Combinations of a Phone NumberBuild a digit-to-letters map and DFS one digit per depth, appending each mapped letter. Record the built string when its length equals the number of input digits.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA One digit per DFS depth, one letter per branch

RECIPE Build the digit→letters map, then DFS

COST Complexity & alternatives

RUN IT DFS one digit per depth, append each mapped letter

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _