13. Tries

Key Insight

A Trie (prefix tree) enables $O(L)$ insert, search, and prefix operations where $L$ is word length — vs $O(L)$ average but $O(L \cdot n)$ worst-case for hashing all words. Use it when you need prefix queries or dictionary lookups over large word sets.

13.1 Trie Implementation

class TrieNode:
    __slots__ = ("children", "is_end", "count")
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end: bool = False
        self.count: int = 0   # words passing through this node

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
            cur.count += 1
        cur.is_end = True

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.is_end

    def starts_with(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

    def count_prefix(self, prefix: str) -> int:
        """Number of inserted words that start with prefix."""
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return 0
            cur = cur.children[c]
        return cur.count

    def delete(self, word: str) -> bool:
        def _delete(node: TrieNode, word: str, depth: int) -> bool:
            if depth == len(word):
                if not node.is_end:
                    return False
                node.is_end = False
                return len(node.children) == 0
            c = word[depth]
            if c not in node.children:
                return False
            should_delete = _delete(node.children[c], word, depth+1)
            if should_delete:
                del node.children[c]
                return not node.is_end and len(node.children) == 0
            return False
        return _delete(self.root, word, 0)

---

13.2 Wildcard Search & Word Board

# --- Word Dictionary with wildcard '.' (can match any letter) ---
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node: TrieNode, i: int) -> bool:
            if i == len(word):
                return node.is_end
            c = word[i]
            if c == '.':
                return any(dfs(child, i+1) for child in node.children.values())
            if c not in node.children:
                return False
            return dfs(node.children[c], i+1)
        return dfs(self.root, 0)

# --- Word Search II (find all words from list on board) ---
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    trie = Trie()
    for w in words:
        trie.insert(w)

    rows, cols = len(board), len(board[0])
    result: set[str] = set()

    def dfs(node: TrieNode, r: int, c: int, path: str):
        if node.is_end:
            result.add(path)
        ch = board[r][c]
        board[r][c] = '#'   # mark visited
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0<=nr<rows and 0<=nc<cols and board[nr][nc] != '#':
                nxt = board[nr][nc]
                if nxt in node.children:
                    dfs(node.children[nxt], nr, nc, path+nxt)
        board[r][c] = ch    # restore

    for r in range(rows):
        for c in range(cols):
            if board[r][c] in trie.root.children:
                dfs(trie.root.children[board[r][c]], r, c, board[r][c])
    return list(result)

---

13.3 Key CP Patterns

Pattern	When
Prefix queries	Count words with prefix, autocomplete
Bitwise Trie	Maximum XOR of two numbers (insert bits MSB→LSB)
Wildcard search	'.' matches any character → DFS through Trie
Word board search	Trie prunes impossible prefixes early vs naive backtrack

# --- Maximum XOR of two numbers — Bitwise Trie --- O(n * 32)
class BitTrie:
    def __init__(self):
        self.root = {}

    def insert(self, num: int) -> None:
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in node:
                node[bit] = {}
            node = node[bit]

    def max_xor(self, num: int) -> int:
        node = self.root
        xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            want = 1 - bit
            if want in node:
                xor |= (1 << i)
                node = node[want]
            else:
                node = node[bit]
        return xor

def find_max_xor(nums: list[int]) -> int:
    t = BitTrie()
    for x in nums:
        t.insert(x)
    return max(t.max_xor(x) for x in nums)

---