Frontend Beauty
ESC

Type to search the knowledge base.

Letter Combinations Phone Number

Map digits 2-9 to letters and backtrack all strings — BFS build alternative, empty input, and pruning none needed.

intermediate3 min read
  • dsa
  • backtracking
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Digits string (2–9). Return all letter combinations like phone keypad. Order free.

"23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]
"" → []

Keypad map

2 abc  3 def  4 ghi  5 jkl
6 mno  7 pqrs 8 tuv  9 wxyz

Brute

Nested loops only work for fixed length. Variable length ⇒ backtracking or iterative product.

Backtracking

const MAP: Record<string, string> = {
  "2": "abc",
  "3": "def",
  "4": "ghi",
  "5": "jkl",
  "6": "mno",
  "7": "pqrs",
  "8": "tuv",
  "9": "wxyz",
};

function letterCombinations(digits: string): string[] {
  if (!digits.length) return [];
  const res: string[] = [];
  const path: string[] = [];

  function dfs(i: number) {
    if (i === digits.length) {
      res.push(path.join(""));
      return;
    }
    for (const ch of MAP[digits[i]]) {
      path.push(ch);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(0);
  return res;
}
Time O(4^n · n) n = length, 4 = max letters (7/9)
Space O(n) stack + output

Iterative BFS product

function letterCombinationsBfs(digits: string): string[] {
  if (!digits.length) return [];
  let cur = [""];
  for (const d of digits) {
    const next: string[] = [];
    for (const prefix of cur) {
      for (const ch of MAP[d]) next.push(prefix + ch);
    }
    cur = next;
  }
  return cur;
}

Same asymptotics; sometimes easier to explain as Cartesian product.

Edge cases

  • Empty digits → [] (not [""])
  • Single digit
  • Includes 7/9 (4 letters)
  • Long digits — output size explodes; mention it

Common mistakes

  • Returning [""] for empty input
  • Hardcoding only 3-letter digits
  • Not resetting path (backtracking pop)

Interview delivery

  1. Keypad map.
  2. Backtrack by index.
  3. Empty → [].
  4. Complexity 4^n.
  5. Optional iterative product.

Mental model

Cartesian product of letter groups. Backtracking assigns one digit’s letter at a time; BFS multiplies prefixes by the next group’s letters. Same output.

Size of output

n digits, up to 4 letters → ≤ 4^n strings each length n. Always mention output-sensitive complexity so “O(1)” jokes don’t happen.

Mapping table (say you know 7 and 9)

7→pqrs, 9→wxyz; others three letters. Hardcoding only abc/def is a bug.

Out-loud answer

“Map digits to letters. Backtrack by index; at end join path. Empty input returns []. Iterative product is fine too. Time O(4^n · n).”

Edge-case checklist (run before you say done)

  1. digits = "" → [] not [""].
  2. digits = "2" → ["a","b","c"].
  3. Includes "7" or "9" → four letters each.
  4. Longer strings: don’t try to hardcode nested loops for length 4 — recursion/product scales.
  5. Constraints usually exclude 0 and 1; if they appear, map them to empty and combinations collapse correctly.

Interview delivery

  1. Restate keypad mapping.
  2. Empty input special case first.
  3. Backtracking or iterative product.
  4. Complexity with 4^n.
  5. Offer to print one path on the board for "23".

Further reading