Letter Combinations of a Phone Number

Problem

On a classic phone keypad the digits 2 through 9 each map to a group of letters (2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz). Given a string of such digits, return every string that can be spelled by picking one letter for each digit in order. If the input is empty, return an empty list. Output order does not matter.

• The digit string is up to 5 characters (empty allowed).
• Every character of digits is in '2'..'9'.

Examples

• digits = "68" → ["mt","mu","mv","nt","nu","nv","ot","ou","ov"]. 3 choices for 6 times 3 choices for 8.
• digits = "" → []. No digits means no strings, not the empty string.
• digits = "4" → ["g","h","i"]. One digit with three letters.

Hints

1. Each digit independently contributes one letter. How many total strings is that, and how would you build each one position by position?
2. Keep a partial string; for the current digit, try each of its letters and move on to the next digit.
3. Backtracking over digit positions (choose a letter, recurse, remove it), or iteratively expand a list by one digit at a time.