Store words character-by-character to instantly look up prefixes and autocomplete.
A Trie (Prefix Tree) is a tree where each node represents a single character. Words that share the same prefix share the same path down the tree. This makes searching for a word (or finding all words that start with "auto") extremely fast—taking only O(L) time where L is the length of the word, regardless of how many millions of words are in the dictionary.
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def insert(self, word):
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_word = True