36. Letter Combinations of a Phone Number

Q: Why is the output exponential?

Each digit multiplies the count by 3 or 4 letters. For 4 digits that's at most 4^4 = 256 combinations.

Q: Iterative or recursive?

Recursive is more typical for backtracking. Iterative trades the call stack for explicit list maintenance. Either is fine — Plaid grades clarity.

mediumAsked at Plaid

Generate all letter combinations that a phone-number string could represent. Plaid asks this as a backtracking warm-up before harder combinatorial problems on transaction-tag suggestions.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Plaid loops.

Glassdoor (2025)— Plaid SWE II screen.
LeetCode Discuss (2026)— Plaid OA — backtracking baseline.

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

[]

Approaches

1. Iterative product

Maintain a list of partial strings. For each digit, expand each partial by each letter.

Time: O(4^n * n)
Space: O(4^n * 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 partial of out) for (const ch of map[d]) next.push(partial + ch);
    out = next;
  }
  return out;
}

Tradeoff: Works fine. Allocates intermediate lists per digit.

2. Backtracking

DFS with a path buffer. Push a letter, recurse on the next digit, pop, try the next letter.

Time: O(4^n * n)
Space: O(n) recursion + output

function letterCombinations(digits) {
  if (!digits) return [];
  const map = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
  const out = [];
  function bt(i, path) {
    if (i === digits.length) { out.push(path); return; }
    for (const ch of map[digits[i]]) bt(i + 1, path + ch);
  }
  bt(0, '');
  return out;
}

Tradeoff: Clean recursion. O(n) auxiliary recursion stack instead of intermediate lists.

Plaid-specific tips

Plaid uses this to verify your backtracking template. Bonus signal: discuss the trade-off between iterative (cleaner allocation) and recursive (cleaner code). Connect to their fuzzy-merchant-name expansion where one input merchant can produce a tree of normalized candidates.

Common mistakes

Returning [''] for empty input instead of [].
Including 1 in the map — it has no letters.
Concatenating in a way that grows quadratically (path = path + ch is fine here for small n).

Follow-up questions

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

Generate parentheses (LC 22) — similar backtracking shape.
Permutations (LC 46).
Subsets (LC 78).

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 output exponential?

Each digit multiplies the count by 3 or 4 letters. For 4 digits that's at most 4^4 = 256 combinations.

Iterative or recursive?

Recursive is more typical for backtracking. Iterative trades the call stack for explicit list maintenance. Either is fine — Plaid grades clarity.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →