Letter Combinations of a Phone Number

Examples

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

2 maps to a/b/c and 3 maps to d/e/f, so every pairing of one letter from each gives 3 x 3 = 9 combinations.

Input: digits = ""
Output: []

No digits means no combinations at all.

Input: digits = "2"
Output: ["a","b","c"]

A single digit just gives its own letters, one per combination.

Constraints

• 0 <= digits.length <= 4

• Each character of digits is between "2" and "9".

Approach

Each digit in the input contributes exactly one letter to the final string, chosen from that digit's handful of possible letters. The full answer is every way of picking one letter per digit, in order.

One way to build this is level by level: start with a list containing just the empty string, and for each digit in turn, replace that list with a new one where every existing partial combination has been extended by every letter that digit allows. After processing every digit, the list holds every complete combination.

A more memory-efficient way builds one combination at a time instead of keeping a whole intermediate list alive at every step: pick a letter for the current digit, move on to the next digit, and once every digit has a letter, record the finished combination. Then back up - try the next letter for the digit you most recently picked - which is the same choose/explore/undo rhythm you've seen in every other backtracking problem, just working through digits instead of array positions.

Solutions

Iterative — Build Up Combinations Level by Level

Keep a running list of partial combinations, starting with just the empty string. For each digit, build a brand-new list by taking every partial combination built so far and appending every letter that digit maps to. After the last digit, the list holds every full combination.

function letterCombinations(digits) {
  if (digits.length === 0) return [];

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

  let combinations = [""];

  for (const digit of digits) {
    const letters = digitToLetters[digit];
    const next = [];

    for (const combo of combinations) {
      for (const letter of letters) {
        next.push(combo + letter);
      }
    }

    combinations = next;
  }

  return combinations;
}

Time: O(n * 4^n), where n is the number of digits · Space: O(n * 4^n) for the intermediate and final combination lists

Optimal — Backtracking, One Combination at a Time

Build a single combination in a running string as you move digit by digit. At each digit, try every letter it maps to: append the letter, recurse into the next digit, then remove the letter before trying the next one. Record the running string once every digit has been given a letter.

function letterCombinations(digits) {
  if (digits.length === 0) return [];

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

  const result = [];
  let current = "";

  function backtrack(index) {
    if (index === digits.length) {
      result.push(current);
      return;
    }

    const letters = digitToLetters[digits[index]];
    for (const letter of letters) {
      current += letter;
      backtrack(index + 1);
      current = current.slice(0, -1); // undo
    }
  }

  backtrack(0);
  return result;
}

Time: O(n * 4^n) · Space: O(n) auxiliary (recursion depth + the running string), plus output storage