#17 - Letter Combinations of a Phone Number

MediumBacktracking

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent (phone keypad mapping). Return the answer in any order.

Input	Output
digits = "23"	["ad","ae","af","bd","be","bf","cd","ce","cf"]
digits = ""	[]
digits = "2"	["a","b","c"]

Solution Space

Try it

/**
 * Returns all letter combinations for the given phone digits.
 *
 * @param digits String of digits '2'-'9'
 * @returns All possible letter combinations
 */
export function letterCombinations(digits: string): string[] {
  if (!digits) return [];

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

  const result: string[] = [];

  function backtrack(index: number, current: string): void {
    if (index === digits.length) {
      result.push(current);
      return;
    }
    for (const ch of map[digits[index]]) {
      backtrack(index + 1, current + ch);
    }
  }

  backtrack(0, "");
  return result;
}

Approach: backtracking – for each digit, branch into all its mapped letters and recurse on the next digit.

Time: O(4^n · n) – at most 4 letters per digit, n digits, and O(n) to build each string.

Space: O(n) – recursion depth equals the number of digits (output not counted).

Alternative approaches:

Approach	Idea	Time	Space
Iterative (BFS-like) expansion	Start with [""]; for each digit, append every mapped letter to every existing string	O(4^n · n)	O(4^n · n)

Why backtracking is preferred: teaches the generalizable pattern used in Combination Sum, N-Queens, etc. The iterative approach is equally valid but less transferable as a technique.

#2300 Successful Pairs of Spells and Potions

#39 Combination Sum