17. Letter Combinations of a Phone Number
On an old phone keypad every digit from 2 through 9 carries a group of letters:
| key | letters | key | letters |
|---|---|---|---|
| 2 | a b c | 6 | m n o |
| 3 | d e f | 7 | p q r s |
| 4 | g h i | 8 | t u v |
| 5 | j k l | 9 | w x y z |
You receive a string digits made only of characters 2–9 (it may be empty). Build every word you can spell by choosing one letter for each digit, in the order the digits appear, and return them all as a list of strings.
Return the list in alphabetical (lexicographic) order — walking each key's letters in their printed order already produces exactly that. If digits is empty, return an empty list.
Example 1:
Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explanation: Key 2 offers a/b/c for the first letter and key 3 offers d/e/f for the second, giving 3 × 3 = 9 words in alphabetical order.
Example 2:
Input: digits = "8"
Output: ["t", "u", "v"]
Explanation: A single key 8 spells one-letter words only: t, u, and v.
Constraints:
- 0 ≤ digits.length ≤ 4
- Every character of digits is one of 2, 3, 4, 5, 6, 7, 8, 9.
Hints:
Start from a hard-coded map digit → letters. The answer is the cartesian product of one letter group per digit.
Recursion writes itself: keep a partial word; at position i, try each letter of digits[i], recurse to i + 1, and record the word once every digit has contributed a letter.
No recursion needed either — start from a list holding the empty string and, for each digit, rebuild the list by extending every existing prefix with every letter of that key.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: digits = "23"
Expected output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]