Letter Combinations of a Phone Number

Medium#17letter by letter

On an old phone keypad each digit from 2 to 9 stands for three or four letters. You get a string of such digits; return every word you can type with it, one letter per digit, in any order, and nothing for an empty string. Our example: "38", where 3 is d, e, f and 8 is t, u, v, gives 9 words: dt, du, dv, et, eu, ev, ft, fu, fv.

17 Letter Combinations of a Phone NumberWalkthrough · 1×

Example: every word typed by "38". Watch the step after dv is saved: d is removed, and e takes its first place for the next three words.

[ ]ddtdudveeteuevfftfufv3→def8→tuvpath—results—
not reached yeton the way here; letter in the paththis stepsaved wordfinished or just removed

Spell every word the keys 38 can type

01/57
restart · back · play · step
Speed
1function letterCombinations(digits):
2 if digits is empty: return []
3 path = []
4 results = []
5 spell(0)
6 return results
7
8function spell(i):
9 if i == len(digits):
10 add path joined to results
11 return
12 for letter in letters of digits[i]:
13 path.add(letter)
14 spell(i + 1)
15 path.removeLast()
state
i
–
letter
–
path
–
results
–
click a step to go back

← → step · space play/pause

Why it works

  1. Call i chooses the letter for digit i and hands the rest to call i + 1, so the tree has one level per digit and one branch per letter: every word is one path from the root to a leaf.
  2. Removing the letter after the call comes back frees its place, so the next letter of the same digit is tried with the same letters before it.
  3. A word is saved only when i reaches the end, so it always has exactly one letter per digit.

Complexity

Time O(n × 4ⁿ) for n digits: up to 4ⁿ words, each joined in n steps. Memory O(n) besides the answer: the path and the call stack are n deep.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.