17. Letter Combinations of a Phone Number

Quick Identifier

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

Quick Sights

Time Complexity: O(number of states * cost per state); output-heavy problems are bounded by the number of generated states.
Space Complexity: O(recursion depth) excluding the final output unless stated.
Core Mechanism: Given digits 2-9, map to phone letters and return all letter combinations (cartesian product in digit order).

Concept Explanation

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

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

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

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

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