Tries

A trie (pronounced "try", from retrieval) is a tree built specifically to store a set of strings so that anything to do with their prefixes is fast. Instead of storing each word as an opaque blob the way a hash set does, a trie decomposes every word into its characters and lays them out along root-to-node paths. Each node represents "the strings that share this prefix," and it holds two things: a map from the next character to a child node (children: dict[str, TrieNode]), and a boolean flag, usually called is_end_of_word, that marks whether the path from the root to this exact node spells out a complete word in the dictionary, not merely a prefix of a longer one.

Because every node in the tree corresponds to a prefix, inserting a word just walks (or creates) one child per character and flips the flag on the final node. Looking up a word or a prefix is the same walk: follow children character by character, and if you ever need a child that doesn't exist, the word or prefix isn't there. Both operations take O(L) time, where L is the length of the word or prefix, and — critically — that cost does not depend on how many other words are stored in the trie. A hash set of a million words still answers "is this word present" in roughly O(L) time too, but it cannot answer "does any word start with this prefix" without scanning, because a hash of a whole string gives you no information about partial matches. A trie answers startsWith with the exact same O(L) walk used for search, just without checking the end-of-word flag at the last step. That's the core reason tries beat hash sets whenever the query is about prefixes rather than only exact matches: autocomplete, spell-check suggestions, IP routing tables, and — as you'll see in this subject — wildcard search and word-search-on-a-board all reduce to walking or branching over shared prefixes.

A minimal trie in pseudocode:

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

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end_of_word = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end_of_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Once you have this skeleton, two extensions come up constantly in interviews. The first is wildcard search: a query like "c.t" should match "cat", "cot", "cut", and so on, where . matches any single character. You can't do this with a simple loop anymore because a . forks the search into every child at that position, so you switch to DFS: at each character, if it's a literal, follow the one matching child (or fail); if it's ., recursively try every child and return true if any branch succeeds. The second is searching a 2D board: given a grid of letters and a list of target words, you build one trie from all the words up front, then run DFS/backtracking from every cell, walking both the board and the trie in lockstep — a board path is only worth continuing if the letters seen so far are a valid prefix in the trie, which lets you prune board paths the instant they stop matching any word, rather than re-scanning the whole word list from every starting cell.

Complexity. Building a trie from a dictionary of total length N (sum of all word lengths) costs O(N) time and O(N) space in the worst case (no shared prefixes), though shared prefixes reduce actual memory use since common prefixes are stored once. A single insert/search/startsWith costs O(L) for a word of length L. Wildcard search costs O(L) in the best case but can degrade toward O(26^L) if the query is mostly dots and the trie is bushy, since each dot can branch into every child. Board search with backtracking is bounded by O(rows * cols * 4^maxWordLength) in the worst case, but pruning against the trie (and marking cells visited to avoid reusing a letter) keeps it far below that in practice.

Common pitfalls. Forgetting the is_end_of_word marker is the classic bug: without it, search("car") after inserting "carpet" would incorrectly return true, because the walk succeeds even though "car" was only ever a prefix, never itself inserted as a word. Another frequent mistake is not pruning DFS early during wildcard or board search — always check "is this prefix even possible in the trie" before recursing further, rather than building the full candidate string and checking it at the end. On a board, forgetting to mark the current cell as visited (and un-mark it on backtrack) lets a single cell be reused twice in the same word, producing false positives; the standard fix is to temporarily overwrite the cell's letter (or track a visited set) and restore it after the recursive call returns.

This subject covers three problems, in order: implementing a trie from scratch with insert/search/startsWith, extending a trie-backed dictionary to support .-wildcard search via DFS, and combining a trie with board backtracking to find every word from a list that appears on a 2D letter grid.