Skip to main content

36. Letter Combinations of a Phone Number

mediumAsked at Reddit

Generate all letter combinations from a phone-keypad number string. Reddit uses this backtracking problem to test recursive enumeration — the same shape they'd use to enumerate all tag-permutations for ad targeting.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common backtracking warm-up.

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. Note that 1 does not map to any letters.

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 BFS

Start with [''], for each digit expand each existing string by each letter.

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

Tradeoff: Clean and iterative. Works well when memory permits.

2. Backtracking (optimal)

Recurse char-by-char with current prefix. At depth n, append the prefix to results.

Time
O(3^n * 4^m)
Space
O(n) recursion depth
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 result = [];
  function dfs(i, current) {
    if (i === digits.length) {
      result.push(current);
      return;
    }
    for (const c of map[digits[i]]) dfs(i + 1, current + c);
  }
  dfs(0, '');
  return result;
}

Tradeoff: Same total work, less peak memory. Backtracking is the canonical Reddit-favored answer.

Reddit-specific tips

Reddit interviewers want backtracking and a confident discussion of the time complexity (3^n * 4^m where m is the count of digits mapping to 4 letters). Bonus signal: mention the iterative version as an alternative for languages without good recursion.

Common mistakes

  • Returning [''] for empty input (should be []).
  • Forgetting digits like 7 and 9 map to 4 letters.
  • Mutating the prefix instead of passing by value (works in JS strings but trips in mutable-string languages).

Follow-up questions

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

  • Subsets (LC 78) — similar backtracking shape.
  • Permutations (LC 46).
  • Word break (LC 139) — backtrack + memo.

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 the time complexity 3^n * 4^m?

Each digit maps to 3 or 4 letters. n digits with 3 each give 3^n; m digits with 4 each multiply 4^m.

Could memoization help?

No — every output string is distinct, so there's nothing to share.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →