The problem
On an old phone keypad each digit 2–9 stands for 3 or 4 letters. Given a string of digits, return every letter combination it could type.
Input: "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Picture it
Picture typing on an old phone keypad: 2 = abc, 3 = def. For the first digit you choose one of its letters, for the second digit one of its letters, and so on. The decision tree has one level per digit; every path from top to bottom spells one possible text.
How to recognise it
- The answer is every string you can build by picking one option from each position: one letter for each digit.
- The options at each position are independent of the choices at other positions.
- The input is very short (0 to 4 digits), and the output is exponential: up to 4^4 = 256 strings.
- You can draw the answer as a decision tree with one level per digit and 3 or 4 branches per level; each path from top to bottom spells one string.
- Building a string one letter at a time, going back, and trying the next letter is backtracking. Here no choice ever has to be rejected, so it is the plainest form of the pattern.
Start with brute force
Ignore the keypad while building: generate every possible lowercase string of the right length and keep only those whose letters match the digits.
from itertools import product
from string import ascii_lowercase
KEYS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def letter_combinations_brute(digits):
if not digits:
return []
return ["".join(t)
for t in product(ascii_lowercase, repeat=len(digits))
if all(ch in KEYS[d] for ch, d in zip(t, digits))]
There are 26^n candidate strings, so for 4 digits that is 456,976 candidates, each checked, to find at most 256 answers. Each extra digit multiplies the candidates by 26 while the real answers grow by only 3 or 4.
From brute force to the idea
- Find the waste. The brute force builds strings with letters that do not even belong to the digit at that position.
- Go digit by digit.
dfs(i, word)means "wordspells the firstidigits; extend it". Leveliof the tree handlesdigits[i]. - Loop over only the right letters. For each
chinKEYS[digits[i]], calldfs(i + 1, word + ch). Only the 3 or 4 letters on that key are tried. - Stop at the bottom. When
i == len(digits), every digit has a letter, sowordis a finished answer. - No undo is needed.
word + chmakes a new string for each call, so nothing shared has to be restored. This is why the code has nopop. - Guard the empty input. With no digits the problem wants
[], not a list holding one empty string, sodfsis only calledif digits.
This is the key idea: one tree level per digit, with a loop over just that digit's letters.
The key idea
Backtracking over digits; at each level loop over that digit’s letters. 3ⁿ–4ⁿ results.
Python solution
KEYS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def letter_combinations(digits):
res = []
def dfs(i, word):
if i == len(digits):
res.append(word); return
for ch in KEYS[digits[i]]:
dfs(i + 1, word + ch)
if digits: dfs(0, "")
return resIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (all 26^n strings, filtered) | O(n · 26^n) | O(n) per candidate, plus the output |
| Backtracking (shown code) | O(n · 4^n): at most 4^n finished strings, each built by n concatenations | O(n) for the recursion and the current word, plus the output |
For 4 digits that is at most 256 answers against 456,976 candidates for the brute force.
Edge cases
- Empty string: returns
[], thanks to theif digitsguard. - One digit (
"2"): returns["a", "b", "c"]. - Four-letter keys (
"7","9"): return four letters;"7979"returns 256 strings, the maximum for this problem. - Example (
"23"): returns["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"], in that order, because earlier digits vary slowest. - Digits 0 and 1: these are not on
KEYS, so"1"raisesKeyError. The problem only uses digits 2 to 9. KEYSis a module-level constant, defined before the function, and the snippet needs no imports.
Common mistakes
- Removing the
if digitsguard. For""the code then returns[""](one empty string) instead of[]. - Looking up
KEYS[int(d)]when the dictionary keys are strings: every lookup then raisesKeyError. - Thinking the number of answers is 26^n. Each digit has only 3 or 4 letters, so the total is at most 4^n.
You are also given a set of valid words. Return only the combinations that are in it. Describe how you would avoid exploring branches that cannot become a word, then write it if you like.
Compare with our answer
Keep the same tree and add pruning: precompute every prefix of every word. If the letters chosen so far are not a prefix of any word, no extension can be a word, so stop that branch immediately.
def words_from_digits(digits, words):
prefixes = {w[:i] for w in words for i in range(len(w) + 1)}
res = []
def dfs(i, word):
if word not in prefixes:
return
if i == len(digits):
if word in words:
res.append(word)
return
for ch in KEYS[digits[i]]:
dfs(i + 1, word + ch)
if digits:
dfs(0, "")
return res
With words = {"cat", "bat", "act", "at"} and digits "228" it returns ["act", "bat", "cat"]. Worst case time is still O(n · 4^n), but pruning removes most branches on real dictionaries. Space is O(total letters in the words) for the prefix set.
A strong answer mentions: a prefix set, stopping when the current word is not a prefix, and checking the full word only at the bottom.
1. A security tool must list every password that fits a pattern: position 1 is one of {a, b}, position 2 one of {x, y, z}, and position 3 one of {1, 2}. Which approach fits best?
One tree level per position, with a loop over that position's own options, builds exactly 2 × 3 × 2 = 12 strings. Filtering a whole alphabet creates far more candidates, and the other two methods find one answer rather than all of them.
2. What is the time complexity of the shown solution for n digits?
Keys have three or four letters, so the worst case is 4^n leaves, and building each string costs up to n. The letters at different digits do not remove each other, so n! does not apply.
3. A learner deletes if digits: so the code calls dfs(0, "") always. For which input does the result change?
With no digits dfs immediately reaches i == len(digits) and saves the empty word, so the result is [""] rather than []. For other inputs the guard is never needed.
Score 60% or more and the lesson is marked complete.