17. Letter Combinations of a Phone Number

At a Glance

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Apple
Frequency: High
LeetCode: 17

Problem (one-liner)

Given digits 2-9, map to phone letters and return all letter combinations (cartesian product in digit order).

Recognition Cues

Cartesian product / nested choices
Depth equals digit count — classic DFS over layers

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

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

Optimal Solution

Go

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	letters := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	result := []string{}
	path := make([]byte, 0, len(digits))

	var dfs func(depth int)
	dfs = func(depth int) {
		if depth == len(digits) {
			result = append(result, string(path))
			return
		}
		digit := digits[depth] - '0'
		for _, character := range letters[digit] {
			path = append(path, byte(character))
			dfs(depth + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return result
}

JavaScript

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;
}