Skip to main content

36. Letter Combinations of a Phone Number

mediumAsked at Salesforce

Given a string of digits 2-9, return all possible letter combinations from a phone keypad. Salesforce uses this as the canonical backtracking warmup.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this to test backtracking comfort before harder enumeration problems.
  • LeetCode Discuss (2025-09)— Asked alongside permutations and combinations.

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

Start with [""]; for each digit, replace with cross-product of current results × letters.

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 s of result) for (const c of map[d]) next.push(s + c);
    result = next;
  }
  return result;
}

Tradeoff: Iterative cross-product is concise but allocates intermediate arrays. Acceptable in interview.

2. Backtracking DFS

Recurse digit by digit; pass the current path; emit when path is complete.

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

Tradeoff: Idiomatic backtracking. Salesforce uses this template for their workflow-engine path enumeration.

Salesforce-specific tips

Salesforce uses backtracking templates in their workflow-engine for path enumeration (which steps to fire given a state). They grade on whether you reach for backtracking by default. Bonus signal: discuss that the empty-input edge case must return `[]`, NOT `[""]` — the latter is a common bug.

Common mistakes

  • Returning [""] for empty input instead of [].
  • Not handling the '1' digit (no letters) — though the constraints say 2-9 only, mention it.
  • Using path.push/pop instead of immutable concat — works but pop-after-push is easy to forget.

Follow-up questions

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

  • Combinations (LC 77).
  • Permutations (LC 46).
  • If the keypad mapping is custom (e.g., a phonetic keyboard), generalize.

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 letters (2,3,4,5,6,8) or 4 letters (7,9). If n digits have 3 letters and m have 4, the cross product is 3^n * 4^m.

Iterative or recursive — which does Salesforce prefer?

Either. They want to see you reach for backtracking instinctively; the iterative version is fine but feels less idiomatic for enumeration.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →