Before smartphones, you typed “hello” by pressing 4-3-5-5-6 — five keys for five letters. Each key carried three or four letters. Without the dictionary that T9 predictive text layered on top, those five presses could spell a LOT of different 5-letter strings. Your Nokia computed that number and picked the likeliest word in under 50 milliseconds.
Let's pick a simpler version of the puzzle. 4-3-5-5 — four keys. Each one maps to three letters (4⟶ghi, 3⟶def, 5⟶jkl, 5⟶jkl). How many distinct 4-letter strings could those 4 keys spell, before any dictionary filters them down?
I overthought this problem for ten minutes before the shape clicked. I kept looking for a “clever” rule that would prune most of the combinations. There isn't one. Every path the phone considers IS a valid combination — the dictionary is what makes some of them more likely. The lesson isn't an algorithm; it's recognizing that sometimes the job is just to visit every leaf.
Given digits "23", return every 2-letter combo where letter 1 ∈ abc and letter 2 ∈ def.
81 possible 4-letter strings. Your Nokia picked the right one via its dictionary — but without the dictionary, that's 81 candidates. We'll do the smaller version ('23' ⟶ 9) first, then scale up.