Skip to main content

36. Letter Combinations of a Phone Number

mediumAsked at Workday

Given a string of digits 2-9, return all letter combinations the digits could represent. Workday uses this for backtracking fluency — the same shape as enumerating valid permission combinations across role tiers.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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 product expansion

Start with ['']. For each digit, expand every prefix by each letter.

Time
O(4^n)
Space
O(4^n)
function letterCombinations(digits) {
  if (!digits) return [];
  const map = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
  let out = [''];
  for (const d of digits) {
    const next = [];
    for (const prefix of out) for (const c of map[+d]) next.push(prefix + c);
    out = next;
  }
  return out;
}

Tradeoff: Clean iterative — no recursion stack.

2. Backtracking

Recursive build with index pointer. Base case: index == digits.length, push current.

Time
O(4^n)
Space
O(n) recursion)
function letterCombinations(digits) {
  if (!digits) return [];
  const map = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
  const result = [];
  function backtrack(i, current) {
    if (i === digits.length) { result.push(current); return; }
    for (const c of map[+digits[i]]) backtrack(i + 1, current + c);
  }
  backtrack(0, '');
  return result;
}

Tradeoff: Idiomatic backtracking. Easier to extend (pruning, constraints) than iterative.

Workday-specific tips

Workday accepts either iterative or recursive. The empty-input edge case is the gotcha — return []. Mention the upper bound 4^n explicitly when stating complexity.

Common mistakes

  • Returning [''] for empty input instead of [].
  • Hardcoding 'abc' instead of map lookup — fragile for digit 7 (pqrs, 4 letters).
  • Mutating a shared 'current' string and forgetting to backtrack.

Follow-up questions

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

  • Generate Parentheses (LC 22) — similar backtracking shape.
  • Combinations (LC 77).
  • What if some letters are blacklisted?

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 4^n upper bound?

Digits 7 and 9 have 4 letters. So the worst case is all 7s/9s — 4 choices per digit.

Should I prune?

No constraints to prune against in this problem. If you added 'must form a dictionary word', then trie-based pruning becomes valuable.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →