Letter Combinations of a Phone Number

The key idea

Each digit multiplies the number of combinations by the count of letters it maps to. Build every combination by choosing one letter per digit in order — a depth-first walk of the choice tree where the depth equals the number of digits.

Problem

Given a string digits 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

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

Input: digits = "" Output: []

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

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →