Letter Combinations of a Phone Number

MediumBacktrackingHash TableStringBacktracking

Problem

Given a string of digits from 2 through 9, where each digit maps to a set of letters the way it did on an old telephone keypad, return every possible letter string formed by picking one letter for each digit, in order.

Example. For input "23", digit 2 maps to a, b, c and digit 3 maps to d, e, f, so the output is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Key idea

Each digit contributes an independent choice among a few letters, and the output needs every combination across all digits in sequence, so this is position-by-position backtracking once the keypad mapping is available as a lookup table.

Process the digits left to right, keeping a partial string built from the letters chosen so far. At the current digit, loop over each letter it maps to, append that letter to the partial string, recurse to handle the remaining digits, then remove the letter again before trying the next option (backtracking), so sibling branches build from the same clean partial string. Once every digit has been assigned a letter, the partial string is a complete combination and gets recorded. An empty input string should simply produce no combinations, since there is no digit to anchor a first letter.

Solution

function letterCombinations(digits: string): string[] {
  // No digits means no combinations, not one empty combination.
  if (digits.length === 0) {
    return [];
  }

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

  const result: string[] = [];
  let partial = '';

  function backtrack(index: number): void {
    if (index === digits.length) {
      result.push(partial);
      return;
    }

    // Digits 7 and 9 map to four letters; the rest map to three.
    const letters = digitToLetters[digits[index]];
    for (const letter of letters) {
      partial += letter;
      backtrack(index + 1);
      // Undo the last letter before trying the next option for this digit.
      partial = partial.slice(0, -1);
    }
  }

  backtrack(0);
  return result;
}

Complexity

  • Time: O(4ⁿ · n). Each of the n digits contributes at most 4 letters (digits 7 and 9 map to four), so branching is bounded by 4, and each complete combination costs O(n) to build.
  • Space: O(n). Recursion depth matches the number of digits.

Watch out for

  • Handle the empty input explicitly; the natural recursion can otherwise emit a spurious empty-string result instead of an empty list.
  • Digits 7 and 9 map to four letters instead of three; assuming a uniform three-way branch undercounts the output.

Pattern

This is position-by-position backtracking over independent, per-position choice sets: the same shape used in Subsets and Permutations, but with a variable number of options per step rather than a fixed binary or ordering choice.

Related questions