84. Letter Combinations of a Phone Number

Medium · Backtracking

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. The mapping of digits to letters follows the standard telephone keypad: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz.

Return the combinations in lexicographic (alphabetical) order. If the input is an empty string, return an empty array.

This is a classic backtracking problem where you explore all possible combinations by building strings one character at a time, choosing from the letters mapped to each digit.

Examples

Example 1
Input: "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: Digit 2 maps to ['a','b','c'] and digit 3 maps to ['d','e','f']. Combining each letter from 2 with each letter from 3 gives 9 combinations in lexicographic order.
Example 2
Input: "9"
Output: ["w","x","y","z"]
Explanation: A single digit 9 maps to ['w','x','y','z'], so the result is just those four letters.

Constraints