Trie
Applies to: general, python
A trie (prefix tree) stores strings as paths of characters from a root, so words sharing a prefix share nodes. Lookups cost O(length) no matter how many words are stored, which makes it ideal for autocomplete and prefix search.
node = root
for ch in word:
node = node.setdefault(ch, {})
node["quot;] = True # mark end of a word