Prefix Search

The Idea

Autocomplete asks a different question from "is this a word?". It asks "what starts with this?".

Walk the prefix once — that costs one hop per typed character. The node you land on is the root of a subtree holding exactly the words with that prefix, so gathering the suggestions never touches the rest of the dictionary.

Real-World Example

A phone keyboard suggesting words after three letters. It cannot rescan 200,000 words between keystrokes, so it keeps the position it reached for "cat" and, on the next key, takes one more hop instead of starting over.

The Code

trie = {"c": {"a": {"r": {"$": 1, "t": {"$": 1}}, "t": {"$": 1}}}}
def walk(prefix):                  # O(len(prefix)) — dictionary size is irrelevant
    node = trie
    for ch in prefix:
        if ch not in node: return {}
        node = node[ch]
    return node

def collect(node, so_far, out):
    if "$" in node: out.append(so_far)
    for ch in node:
        if ch != "$": collect(node[ch], so_far + ch, out)
    return out

print(collect(walk("ca"), "ca", []))   # every word under the 'ca' branch

trie = {"a": {"t": {"$": 1}}}
node = trie
for ch in "ax":
  node = node.get(ch)
  if node ___ None:
      break
print(node)   # None