Letter Combinations of a Phone Number

Generate all possible letter combinations for a string of digits using a phone keypad.

recursion backtracking string mapping

You are given a string `digits` containing digits from '2' to '9' inclusive. Return all possible letter combinations that the number could represent, in any order.

A mapping of digit to letters (just like on a telephone keypad) is given below:
- 2: abc
- 3: def
- 4: ghi
- 5: jkl
- 6: mno
- 7: pqrs
- 8: tuv
- 9: wxyz

Note that the digit '1' does not map to any letters. But the input will only contain digits '2'-'9'. Implement a function:

`def letter_combinations(digits: str) -> list[str]:`

The result should be a list of strings, each of length `len(digits)`, containing all combinations in any order. For example, if `digits = "23"`, the possible combinations are `["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]`.

**Edge case:** If `digits` is an empty string, return an empty list `[]`.

Constraints

- `0 <= len(digits) <= 4`
- `digits[i]` is a digit from `'2'` to `'9'` inclusive.
- The number of combinations is at most `4^4 = 256`.

Example

```python
# Example 1
print(letter_combinations("23"))
# Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

# Example 2
print(letter_combinations("")))
# Output: []

# Example 3
print(letter_combinations("2"))
# Output: ['a', 'b', 'c']
```

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a mapping from digit to string of possible letters.

Try a recursive approach: for each digit, branch over its letters and append them to a partial combination.

If recursion is not your style, an iterative solution with a list of current combinations works: for each digit, extend every current combination with each possible letter.

Remember the empty case: return an empty list, not `['']`.

The order of the output does not matter, but make sure the length of each combination equals the number of digits.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.