Letter Combinations of a Phone Number
HardOne digit per level, a branch per letter
Problem
Given digits 2-9, return all letter combinations they could spell on a phone keypad.
Like an odometer: for each digit, branch into its letters and extend every combination so far.
The idea
The digit at depth i determines which letters branch at that level, so the recursion depth equals the number of digits and each leaf is one full combination. It is a plain cartesian product expressed as a tree walk.
The trick
- Depth = number of digits; branching = letters on that digit.
- Digits 7 and 9 have four letters, the rest have three.
- An empty input yields an empty list, not a list containing an empty string.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — '23' Values: 23.
1map digit->letters2f(i, cur):3 if i==len(digits): output cur; return4 for ch in letters[digits[i]]:5 f(i+1, cur+ch)Input
- array
- [23]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- digits = "23"
- Output:
- ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
- Explanation:
- Each digit's letters combine with the next's.
Example 2
- Input:
- digits = "2"
- Output:
- ['a', 'b', 'c']
- Explanation:
- a, b, c.
Example 3
- Input:
- digits = ""
- Output:
- []
- Explanation:
- No digits → no combinations.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.