3.9

Telephone-keypad mapping
2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz

Algorithm
1. Build a dictionary digit_for that maps every lowercase letter a-z to its digit.
2. For every word in the given word-list:   a. Skip it if its length ≠ length of the digit sequence.   b. Convert each letter to its digit with digit_for; stop early on any mismatch.   c. If the whole word converts exactly to the digit string, emit the word.

Pseudocode
digit_for = {a:2,b:2,c:2, d:3,…, z:9} // as listed above
function t9_match(digits, words):
  out = []
  for w in words:
    if len(w) != len(digits): continue
    ok = True
    for i,ch in enumerate(w):
      if digit_for[ch] != digits[i]: ok = False; break
    if ok: out.append(w)
  return out

Python reference implementation
def t9_words(digits: str, words: list[str]) -> list[str]:
pad = {'a': '2','b': '2','c': '2','d': '3','e': '3','f': '3',
'g': '4','h': '4','i': '4','j': '5','k': '5','l': '5',
'm': '6','n': '6','o': '6','p': '7','q': '7','r': '7','s': '7',
't': '8','u': '8','v': '8','w': '9','x': '9','y': '9','z': '9'}
res = []
for w in words:
if len(w) != len(digits): continue
if all(pad[ch] == d for ch, d in zip(w.lower(), digits)):
res.append(w)
return res


Complexity
Let n be the number of words and k the digit-string length (typically small). Time = O(n·k) because each word is scanned at most once; Space = O(1) besides the output list.

Example
Input digits = “269”, word-list = {any, box, boy, cow, …}
Output = [any, box, boy, cow] because
  • a→2, n→6, y→9 → 269
  • b→2, o→6, x→9 → 269
  • … and so on.

Back to Chapter 3