Keypad Word Candidates
MediumBacktracking
Problem
On an old phone keypad, each digit from 2 to 9 maps to letters: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz.
Given a string digits, return every letter string the key presses could stand for, in any order. If digits is empty, return an empty list.
Example 1
- Input:
- digits = "23"
- Output:
- ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
3 letters for '2' times 3 letters for '3' gives 9 strings.
Example 2
- Input:
- digits = ""
- Output:
- []
Constraints
- 0 ≤ digits.length ≤ 4
- digits[i] is in '2'..'9'.
Hint
Show the first hint
Each digit contributes exactly one letter, and the choices are independent.
Walkthrough
How to approach it
01Clarify before coding
- Can digits contain 0 or 1? No, only 2–9.
- What does an empty input return? An empty list, not a list with an empty string.
- Output order? Any.
02Brute force
Nested loops, one per digit. That only works when the length is fixed in advance.
Cost: The work, 4^n · n, is unavoidable because it is the output size; the problem is that the loop depth is variable, which recursion solves.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.