017. Letter Combinations of a Phone Number

At a Glance

• Topic: Hash Table
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 017

Problem Statement

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.

Example 1:

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

Example 2:

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

Constraints:

1 <= digits.length <= 4
digits[i] is a digit in the range [&#39;2&#39;, &#39;9&#39;].

Approach & Solution Steps

• Iterative queue — extend strings per digit — O(4^n).
• Optimal — DFS append letter per position — same complexity, simpler reasoning.

Optimal JS Solution

const digitToLetters = [
  '',
  '',
  'abc',
  'def',
  'ghi',
  'jkl',
  'mno',
  'pqrs',
  'tuv',
  'wxyz',
];

function letterCombinations(digits) {
  if (digits.length === 0) {
    return [];
  }
  const result = [];
  const path = [];

  function dfs(depth) {
    if (depth === digits.length) {
      result.push(path.join(''));
      return;
    }
    const options = digitToLetters[Number(digits[depth])];
    for (const character of options) {
      path.push(character);
      dfs(depth + 1);
      path.pop();
    }
  }

  dfs(0);
  return result;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.