If these ideas are new, begin with:
Understand the idea
A prefix trie stores characters on edges. A root-to-node path represents a prefix; a terminal marker indicates a full inserted word. Shared paths reduce repeated prefix storage.
Work through an example
cat and car share c→a, then branch at t/r. The node for ca exists but is not terminal, so exact search for ca must fail.
Time and space complexity
Storage O(total distinct prefix nodes); lookup O(L) expected dictionary work for length L.
Why it works
Each node corresponds to one distinct stored prefix; terminal flags record complete words.
Common mistakes
- An existing path alone does not prove a word exists.
- Empty-string insertion marks the root.
Chapter lab · Python implementation
A trie shares common prefixes rather than repeatedly storing each complete word path. Edges consume characters; a terminal marker distinguishes a complete word from merely a prefix. Our lab inserts cat, car, and dog, then supports exact, prefix, and dot-wildcard matching over code points.
This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.
class Trie:
def __init__(self): self.root={}
def insert(self,word):
node=self.root
for char in word: node=node.setdefault(char,{})
node[None]=True
def locate(self,prefix):
node=self.root
for char in prefix:
if char not in node: return None
node=node[char]
return node
def contains(self,word):
node=self.locate(word)
return node is not None and None in node
def starts_with(self,prefix):
return self.locate(prefix) is not None
def matches(self,pattern):
def visit(node,i):
if i==len(pattern): return None in node
char=pattern[i]
if char=='.':
return any(visit(child,i+1) for key,child in node.items() if key is not None)
return char in node and visit(node[char],i+1)
return visit(self.root,0)Run and test the lab
Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.
t=Trie()
for word in ['cat','car','dog']: t.insert(word)
assert t.contains('cat') and not t.contains('ca')
assert t.starts_with('ca') and not t.starts_with('z')
assert t.matches('c.t') and not t.matches('c..s')
t.insert(''); assert t.contains('')