AdvancedTrees
Tries for prefix questions
A trie stores words letter by letter in a tree, so “does any word start with app?” takes time proportional to the prefix, not the dictionary.
The idea
Each node is a letter and holds children for the next letters. Inserting a word walks or creates nodes; a flag marks where a word ends.
Searching a prefix just walks the letters: if you can, some word has that prefix. The dictionary size doesn't matter.
Worked example
Insert “app” and “apple”, then search
- a → p → p (end) → l → e (end)
- search “app” → reach the end flag → True; startsWith “appl” → path exists → True; search “ap” → no end flag → False
In code (Python)
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True # end of a word
def _walk(self, text):
node = self.root
for ch in text:
if ch not in node:
return None
node = node[ch]
return node
def search(self, word):
node = self._walk(word)
return node is not None and "$" in node
def starts_with(self, prefix):
return self._walk(prefix) is not NoneO(length) per insert or search.
How to spot it
- Autocomplete, “starts with”, many word lookups in a grid (word search II).
Common mistakes
- Forgetting the end-of-word marker, so prefixes count as words.
- Using a trie for a single lookup, where a set is simpler.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →