Tries (Prefix Trees)

🧠 Spot It

• Problem involves prefix matching, autocomplete, word search
• Multiple strings need to be searched efficiently
• Brute force would be O(N × M) — Trie brings prefix lookups to O(M)

---

Trie Node & Implementation

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False

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

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

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

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

---

Pattern 2 — Wildcard Search (Dot = Any Char)

Used when . can match any character. DFS all children when . is encountered.

# LC 211 — Design Add and Search Words Data Structure
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

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

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

---

Pattern 3 — Word Search II (Trie + Grid DFS)

Multiple words, one grid. Build trie from word list. DFS grid following trie paths. Prune dead ends.

# LC 212 — Word Search II
def findWords(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

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

    def dfs(r, c, node, path):
        if node.is_end:
            result.add(path)
            node.is_end = False   # avoid duplicates

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        ch = board[r][c]
        if ch not in node.children:
            return

        board[r][c] = '#'    # mark visited
        child = node.children[ch]
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r + dr, c + dc, child, path + ch)
        board[r][c] = ch     # restore (backtrack)

        if not child.children:    # prune dead trie node
            del node.children[ch]

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root, "")

    return list(result)

Key insight: Pruning (del node.children[ch]) removes exhausted trie branches — avoids revisiting paths where no more words can be found.

---

Senior Tricks

• Use children = [None] * 26 (array) instead of dict for fixed alphabet — faster access
• Store the actual word string at is_end node instead of boolean — avoids path reconstruction
• Prune trie during Word Search II to avoid TLE on large boards
• Trie beats set for prefix queries — set can't answer startswith in O(M)

---

Problems

---

Notes

<!-- Add your own observations as you solve problems -->