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 — Word Search with Backtracking (Trie + DFS)

Used for Word Search II — multiple words on a grid.

# Build trie from word list
# DFS the grid, following trie paths
# Mark visited cells, backtrack after each path

---

Senior Tricks

• Use children = [None] * 26 (array) instead of dict for fixed alphabet — faster
• Store word at is_end node instead of boolean for quick retrieval
• Trie + DFS on grid is the canonical Word Search II approach

---

Problems

---

Notes

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