13. Tries

What Interviewers Test Here

• Recognising prefix-query problems (autocomplete, word search)
• Clean trie insert/search/prefix implementation
• Traversal over trie children

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end: bool = False

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

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

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

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

---

Conceptual Q&A

Q1: "When would you use a Trie instead of a Hash Set for storing words?"

Walkthrough:

"A hash set is simpler and faster for exact-match lookups — $O(L)$ hash computation per word, but conceptually $O(1)$.

Use a Trie when you need prefix operations:

• 'Does any word start with this prefix?' → starts_with() in $O(L)$. A hash set would require iterating all words.
• 'Autocomplete — list all words matching prefix' → DFS from the prefix node. No alternative with a hash set.
• 'Count words with a given prefix' → store counts at each node.

Rule: if the problem mentions prefixes, autocomplete, or common-prefix grouping → Trie. Otherwise → hash set."

---

Q2: "Implement a word search: find all words from a dictionary on a character board."

Walkthrough:

"Brute force: for each word in the dictionary, run DFS from every cell. $O(W \cdot M \cdot N \cdot 4^L)$ — very slow.

Optimised: build a Trie of all dictionary words. Then do one DFS from each cell, navigating the Trie simultaneously. If the current prefix isn't in the Trie, prune immediately. $O(M \cdot N \cdot 4^L)$ — the Trie prunes invalid prefixes early."

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])
    found: set[str] = set()

    def dfs(node: TrieNode, r: int, c: int, path: str):
        if node.is_end: found.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] in node.children:
                dfs(node.children[board[nr][nc]], nr, nc, path+board[nr][nc])
        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(found)

---