Wildcards and branching

What is a trie?

A trie, pronounced “try,” is a tree for storing words or other sequences by their prefixes. Each edge advances by one character. Words with the same beginning share a path. A terminal marker records where a complete word ends, since reaching a prefix does not mean that prefix is a stored word.

Example: The words "car" and "cat" share the path c → a. They then branch to r and t, each marked as the end of a word.

Helpful before this chapter

If these ideas are new, begin with:

Strings Hash maps and sets Binary trees

Understand the idea

A wildcard consumes one character while branching across available edges. Exact characters follow one edge; wildcard search explores multiple paths and must still respect the required pattern length.

Work through an example

Pattern c.t matches cat but not car. c.. matches both. A terminal is checked only after all pattern characters are consumed.

Time and space complexity

Work is O(number of visited trie states), potentially exponential in wildcard count, bounded by explored trie nodes.

Why it works

Each recursive call represents precisely the pattern prefix matched by the current trie node.

Common mistakes

A dot here means one code point, not any-length text.
Skip terminal metadata when iterating child edges.

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('')

CHECK YOUR UNDERSTANDING