Skip to main content

36. Letter Combinations of a Phone Number

mediumAsked at Vercel

Given a string of digits 2-9, return all possible letter combinations the number could represent on a phone keypad. Vercel asks this as a classic backtracking warm-up — same recursive shape as enumerating all valid route-segment combinations in their dynamic-segment matcher.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel screen; backtracking expected.
  • Blind (2026-Q1)— Listed in Vercel platform onsite recap.

Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below: 2 -> abc, 3 -> def, 4 -> ghi, 5 -> jkl, 6 -> mno, 7 -> pqrs, 8 -> tuv, 9 -> wxyz.

Constraints

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Examples

Example 1

Input
digits = "23"
Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2

Input
digits = ""
Output
[]

Approaches

1. Iterative BFS expansion

Start with [""]; for each digit, expand each partial result by appending every letter for that digit.

Time
O(4^n * n)
Space
O(4^n)
function letterCombinations(digits) {
  if (!digits) return [];
  const map = { '2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz' };
  let result = [''];
  for (const d of digits) {
    const next = [];
    for (const r of result) {
      for (const c of map[d]) next.push(r + c);
    }
    result = next;
  }
  return result;
}

Tradeoff: Simple to write; allocates intermediate arrays. Equal complexity to backtracking.

2. Backtracking DFS (optimal)

DFS over digit indices, appending each letter and recursing.

Time
O(4^n * n)
Space
O(n) recursion
function letterCombinations(digits) {
  if (!digits) return [];
  const map = { '2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz' };
  const out = [];
  function dfs(i, path) {
    if (i === digits.length) { out.push(path); return; }
    for (const c of map[digits[i]]) dfs(i + 1, path + c);
  }
  dfs(0, '');
  return out;
}

Tradeoff: Single allocation per leaf. Backtracking is the canonical answer Vercel wants — and generalizes to harder enumeration problems.

Vercel-specific tips

Vercel grades for the backtracking shape. Bonus signal: handling the empty-input edge case before recursion, and recognizing that the result has 3^k * 4^j combinations (k digits with 3 letters, j with 4) — useful for estimating runtime out loud.

Common mistakes

  • Returning [''] instead of [] for empty input — wrong.
  • Building the map inside the loop — recreates it on every call.
  • Mutating a shared path array without copying on push — corrupts results.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Generate Parentheses (LC 22) — backtracking with constraints.
  • Combinations (LC 77) — backtracking over choices.
  • What if some digits map to empty (1, 0)? Skip them.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is this 4^n and not 3^n?

Digits 7 and 9 map to 4 letters; the rest map to 3. Worst case is all-7s or all-9s, giving 4^n. The actual count is 3^k * 4^j.

Why backtracking over iterative BFS?

Same complexity, but backtracking uses O(n) stack instead of allocating O(4^n) intermediate arrays. Cleaner shape for follow-ups like constraint pruning.

Practice these live with InterviewChamp.AI

Drill Letter Combinations of a Phone Number and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →