Tries (Prefix Trees)

The idea

A trie stores strings by sharing prefixes: each edge is a character, and a flag marks where a word ends. Insert, search, and prefix checks all run in O(length of the word) — independent of how many words are stored. That prefix-time guarantee is the whole point.

Implementation

class TrieNode:
    def __init__(self):
        self.children = {}        # char -> TrieNode
        self.end = False          # a word ends here

class Trie:
    def __init__(self): self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.end = True
    def search(self, word):
        node = self._find(word)
        return node is not None and node.end
    def starts_with(self, prefix):
        return self._find(prefix) is not None
    def _find(self, s):
        node = self.root
        for c in s:
            if c not in node.children: return None
            node = node.children[c]
        return node

(For a fixed lowercase alphabet, an array children[26] is faster than a dict.)

Wildcard / fuzzy search

When a query has wildcards (. matches any char), you can’t follow a single path — DFS over children at each wildcard:

def search(self, word):
    def dfs(node, i):
        if i == len(word): return node.end
        c = word[i]
        if c == ".":
            return any(dfs(child, i+1) for child in node.children.values())
        return c in node.children and dfs(node.children[c], i+1)
    return dfs(self.root, 0)

This is “Add and Search Word.” Edit-distance fuzzy matching layers DP over the trie traversal.

Trie + grid (search many words at once)

For Word Search II (find many words in a board), building one trie of all the words and DFS-ing the grid against it is far better than searching each word separately: at each cell you advance the trie pointer, pruning the moment no word shares the current prefix. Prune leaves as words are found to keep it fast.

Bitwise trie (numbers)

Store integers as fixed-length bit strings in a binary trie (children 0/1). Walking it to prefer the opposite bit at each step finds the maximum XOR pair in O(n·bits) — “Maximum XOR of Two Numbers.” A surprising, high-signal use.

Complexity and the trade-off

A trie trades memory for prefix power. If you only need membership, a hash set is simpler; reach for a trie the moment prefixes (autocomplete, longest common prefix, prefix counts) matter.

When to use it

• Autocomplete / prefix queries / “starts with” — Implement Trie, search suggestions.
• Wildcard or fuzzy word search — Add and Search Word.
• Many-word search in text/grid — Word Search II, replace-words, word-break with a dictionary.
• Max-XOR / bit problems — bitwise trie.

Pitfalls

• Forgetting the end flag — without it you can’t distinguish a stored word from a mere prefix.
• Memory blowup — many distinct prefixes; use arrays for fixed alphabets and prune found branches.
• Not pruning in grid search — without trie-guided pruning it degenerates to brute force.