noodleProblems/
Letter Combinations of a Phone Number
#27

Letter Combinations of a Phone Number

AlgorithmmediumHash TableStringBacktracking

Given a string digits containing digits from 2 to 9, return every letter combination the number could spell. The combinations may be returned in any order.

The digit-to-letter mapping is the one on a telephone keypad: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz. Note that 1 maps to no letters and never appears in the input.

If digits is the empty string, return an empty array.

Example cases

  • two digits
    in digits = "23"
    out ["ad","ae","af","bd","be","bf","cd","ce","cf"]
    2 → "abc" and 3 → "def"; every pairing of one letter from each gives 3 × 3 = 9 combinations.
  • empty input
    in digits = ""
    out []
    No digits means no combinations.
  • single digit
    in digits = "2"
    out ["a","b","c"]
    One digit returns its own letters as single-character strings.

Constraints

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