Skip to main content

36. Letter Combinations of a Phone Number

mediumAsked at Datadog

Generate all possible letter combinations for a phone-keypad number. Datadog uses this as a backtracking warmup — same recursive-emission structure as their downsampling rollup that enumerates resolution buckets.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog phone screen backtracking problem.
  • LeetCode Discuss (2025-09)— Datadog tagged.

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: 2->abc, 3->def, ..., 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
[]

Example 3

Input
digits = "2"
Output
["a","b","c"]

Approaches

1. Iterative Cartesian product

Start with [""]; for each digit, extend each partial string by each letter.

Time
O(3^n * 4^m)
Space
O(output)
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 out = [''];
  for (const d of digits) {
    const next = [];
    for (const p of out) for (const c of map[d]) next.push(p + c);
    out = next;
  }
  return out;
}

Tradeoff: Works and is arguably cleaner than recursive. But interviewers want to see backtracking too.

2. Backtracking recursion (optimal)

Recurse digit-by-digit. At each level, append one letter to a buffer; recurse; pop. Emit when buffer length equals input length.

Time
O(3^n * 4^m)
Space
O(n) recursion + output
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: Canonical backtracking. Datadog interviewers expect this pattern even if iterative is equivalent — it generalizes to harder problems.

Datadog-specific tips

Datadog grades on whether you can pattern-match this to other backtracking problems (subsets, permutations, combination sum). Articulate the recursion as 'at each digit, branch on each letter' — that's the template for harder follow-ups.

Common mistakes

  • Forgetting the empty-input edge case — returning [''] instead of [].
  • Mutating a shared buffer without popping — corrupts subsequent branches.
  • Hardcoding the digit-to-letter map wrong (7 has 4 letters, 9 has 4 letters — the rest have 3).

Follow-up questions

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

  • Generate Parentheses (LC 22) — same backtracking shape.
  • Combination Sum (LC 39) — backtracking with reuse.
  • Subsets (LC 78) — power-set enumeration.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Iterative or recursive?

Both are O(same). Interviewers often want recursive because it generalizes to harder backtracking. Iterative is fine if you can articulate why.

What about empty input?

Return []. The convention is 'empty input means no combinations,' not '[""]'.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →