Skip to main content

17. Letter Combinations of a Phone Number

medium

Given a string of digits 2-9, return every possible letter combination they could represent on an old-school phone keypad. The canonical first-week introduction to backtracking and Cartesian-product recursion.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Examples

Example 1

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

Example 2

Input
digits = ""
Output
[]

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If digits is empty return [] (not [""]) — this edge case trips up half of all submissions.

Hint 2

Think recursion tree: at depth i pick one letter for digits[i]. The leaves at depth n are your answers.

Hint 3

Backtrack with a current-path buffer. For each letter mapped to digits[index], append it, recurse on index+1, then pop. Push the buffer string to the result when index == digits.length.

Hint 4

No memoization needed — every path is distinct.

Solution approach

Reveal approach

Build a digit-to-letters map (2 -> abc, 3 -> def, ... 9 -> wxyz). Recurse with the current index into the digits string and an accumulator path. Base case: when index == digits.length, append the joined path to the result and return. Recursive case: iterate over the letters mapped to digits[index], append each, recurse to index + 1, then pop (this is the backtrack step that lets the same buffer be reused for the next branch). Handle the empty-string input as a special case before recursing — return [] not a single empty string. Time complexity is O(4^n * n) because each digit contributes up to 4 letters (digit 7 and 9), and the final string of length n is copied to the result. Space is O(n) for the recursion stack plus the output.

Complexity

Time
O(4^n * n)
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • cartesian-product

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

Drill Letter Combinations of a Phone Number and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →