Example 1
ready- Input
digits = "23"- Expected
[ "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" ]- Why
- three choices from 2 combine with three choices from 3
Letter Combinations
35 min · letterCombinations()mediumOpen in LeetCode #17 ↗
One short number can hide a surprising number of words. The digits 23, for example,
can start with any letter on 2 and finish with any letter on 3.
Given a string digits, return every letter string it can spell on this phone keypad:
2 → abc,3 → def,4 → ghi,5 → jkl6 → mno,7 → pqrs,8 → tuv,9 → wxyz
Choose exactly one letter for each digit, and keep the digit order. You may return the
finished strings in any order. When digits is empty, return [].
Constraints
0 <= digits.length <= 7- Every character in
digitsis one of2through9.
Hints
Build one layer at a time
Start with the choices for the first digit. For each later digit, append each of its letters to every partial string you already have.
Think in decisions
At position i, your only decision is which letter mapped from digits[i] comes
next. Once you choose it, move to position i + 1.
Undo after exploring
Add one letter to the current path, explore everything below that choice, then remove
it before trying the next letter. The empty input needs an early return so it produces
[], not a list containing one empty string.
Follow-up
Could you write the search so it stores only the current path, apart from the strings that must be returned?
Visible cases
Examples
Example 2
ready- Input
digits = ""- Expected
[]- Why
- no digits means there is no letter string to build
Example 3
ready- Input
digits = "7"- Expected
[ "p", "q", "r", "s" ]- Why
- 7 maps to four letters
Interview signal
Asked at
AmazonGoogleMeta
Iterative Cartesian product
A Cartesian product combines every choice from one group with every choice from the next. Keep a list of partial strings, then expand it once per digit.
def letter_combinations(digits: str) -> list[str]:
if not digits:
return []
keypad = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
}
combinations = [""]
for digit in digits:
next_combinations = []
for prefix in combinations:
for letter in keypad[digit]:
next_combinations.append(prefix + letter)
combinations = next_combinations
return combinationsIf every digit offers four letters, the answer contains 4ⁿ strings, each of length
n. Time O(4ⁿ · n), space O(4ⁿ · n), including the returned strings.
Backtracking — keep one path
This is the backtracking pattern: make one choice, explore everything that follows,
then undo the choice before trying its neighbor. A list named path holds only the
letters chosen for the current candidate.
def letter_combinations(digits: str) -> list[str]:
if not digits:
return []
keypad = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
}
result: list[str] = []
path: list[str] = []
def search(index: int) -> None:
if index == len(digits):
result.append("".join(path))
return
for letter in keypad[digits[index]]:
path.append(letter)
search(index + 1)
path.pop()
search(0)
return resultEvery leaf is one answer, and joining its n letters costs O(n). Time O(4ⁿ · n) in
the worst case. Space O(n) auxiliary for the path and call stack, excluding the
required output.
The win isn't a smaller output—you must produce every string. Backtracking gives the search a clean shape while keeping unfinished candidates out of a growing table.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" ]
Run: visible + custom · Submit: full suite