Trie LeetCode Pattern Guide — Prefix Search, Autocomplete, and Word Problems

A Trie LeetCode pattern guide is useful because the data structure shows up whenever the brute-force version keeps scanning the same prefixes again and again. Prefix search, autocomplete, dictionary matching, board word search, and wildcard word problems all reward the same move: turn a set of words into a character-by-character decision tree, then walk that tree instead of re-checking every candidate.

The trick is not memorizing one implementation. The trick is learning when a trie changes the shape of the problem. If the input is a dictionary of words and the query is "does anything start with this partial string?", "can I continue this path?", or "what words match this pattern?", a trie can prune work early. That pruning is what separates accepted interview solutions from solutions that time out on the last test case.

The core Trie LeetCode pattern: prefix decisions, not word decisions

A normal hash set answers complete-word questions well: "is apple in the dictionary?" A trie answers incremental questions well: "after reading app, are there any possible words left?" That difference matters in interviews.

| Problem shape | Hash set helps? | Trie helps? | Why | |---|---:|---:|---| | Exact lookup for many words | Yes | Sometimes | Hash set is simpler unless you need prefixes | | Prefix lookup or autocomplete | Weak | Strong | Trie stores shared prefixes once | | DFS on a grid with dictionary words | Weak | Strong | Trie stops dead paths immediately | | Wildcard search like b.. | Weak | Strong | Trie branches only where wildcard appears | | Replace words with shortest root | Possible | Strong | Trie finds first terminal prefix | | Maximum XOR using bits | No | Strong | Bit trie chooses opposite bit greedily |

The mental model: each node represents a prefix. Edges represent the next character. A terminal marker says "a word ends here." Many bugs come from mixing those concepts. The node for app can exist because apple exists, but app is only a word if that node is terminal.

Minimal implementation template

Most LeetCode trie solutions need a node with children and one terminal field. In Python, a dictionary is enough unless the alphabet is fixed and performance is tight.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None       # store full word at terminal nodes
        self.is_end = False    # or use this instead of word

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 = True
        node.word = word

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

    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

A useful interview habit is storing the complete word at terminal nodes. In Word Search II and autocomplete variants, that lets you append node.word without rebuilding strings on every recursive step. It also makes duplicate prevention easy: after adding a found word, set node.word = None so the same word is not emitted twice from a different board path.

When to reach for a trie

Use this decision rule before coding:

1. There is a dictionary or list of strings. The problem gives words, products, roots, usernames, file paths, or binary strings.
2. Queries consume characters gradually. You scan a query left to right, DFS through a board, or test patterns with wildcards.
3. A prefix can prove failure early. If no dictionary word starts with qzx, the search should stop immediately.
4. The same prefixes are reused. Many products start with mobile, many words share pre, or many grid paths share car.

If all four are true, a trie is probably the intended solution. If the problem only asks exact membership, a set is usually cleaner. If it asks sorted lexicographic output and there are few queries, sorting plus binary search may beat a trie in code simplicity.

Pattern 1: Implement Trie / Design Prefix Search

This is the pure template problem. The interviewer is checking node design, terminal markers, and complexity explanation.

Common strong explanation:

• Insert is O(L) for a word of length L because you create or follow one edge per character.
• Search is O(L) for the same reason.
• Space is O(total characters) in the worst case, less when prefixes are shared.
• The terminal marker distinguishes a complete word from a prefix.

Common trap: returning true from search("app") after inserting only "apple". That returns prefix existence, not word existence. Keep search and startsWith separate.

Pattern 2: Autocomplete and search suggestions

Autocomplete problems add two requirements: gather candidates under a prefix, and return them in a required order. There are two main approaches.

Approach A: store top suggestions at each node. While inserting sorted products, append the product to each prefix node until the node has three suggestions. Then each query prefix returns in O(length of prefix) time. This is ideal for LeetCode Search Suggestions System.

Approach B: DFS from the prefix node. Walk to the prefix, then traverse descendants in sorted child order until you collect enough results. This is flexible when the limit changes, but it costs more per query.

For interviews, approach A is usually cleaner when the result limit is fixed. Sort the input first so each node naturally receives lexicographically smallest products.

products.sort()
root = Node()
for product in products:
    node = root
    for ch in product:
        node = node.children.setdefault(ch, Node())
        if len(node.suggestions) < 3:
            node.suggestions.append(product)

Then for each typed character, move one level deeper. If the prefix breaks, all future answers are empty. That "broken prefix stays broken" detail saves awkward edge-case code.

Pattern 3: Word Search II and grid DFS

Word Search II is the trie problem that most clearly rewards pruning. The brute-force version starts from each board cell and compares paths against every word. A trie flips it: build one dictionary tree, then walk board paths only while the current prefix exists.

The recipe:

1. Insert every word into the trie.
2. Start DFS from each board cell.
3. At each step, check whether the character is a child of the current trie node.
4. If not, stop. That path cannot form any word.
5. If the next node has word, record it and clear it to avoid duplicates.
6. Mark the board cell as visited, explore four neighbors, then restore it.

The important pruning line is before recursion, not after. If board[r][c] is not in node.children, return immediately.

A second optimization is deleting leaf nodes after they are exhausted. You can pop a child when it has no children and no terminal word. That is not required for correctness, but it can matter on dense boards and large dictionaries.

Common traps:

• Using a global visited set without removing cells on backtrack.
• Building candidate strings at every step instead of storing word in the terminal node.
• Forgetting duplicate words can be found from multiple paths.
• Searching every word separately with DFS, which often times out.

Pattern 4: Wildcard dictionary search

Problems like Design Add and Search Words allow . to match any character. A hash set struggles because b.. could match many words. A trie makes the wildcard a controlled branch.

Search recursively:

• If the current pattern character is normal, follow that child if it exists.
• If it is ., try every child node.
• At the end of the pattern, return whether the current node is terminal.

The worst case can still branch heavily, especially for patterns like ...., but it only branches through actual stored prefixes. That is the key interview point. You are not generating all strings; you are exploring the dictionary tree.

To reduce work, group roots by word length or store word lengths separately if the problem permits. A wildcard query of length 5 can ignore every terminal path of length 4 or 8. For most LeetCode versions, trie recursion alone passes, but mentioning length pruning signals good judgment.

Pattern 5: Replace Words and shortest root matching

Replace Words gives a dictionary of roots and a sentence. For each word, replace it with the shortest root prefix if one exists. This is a trie-friendly problem because the correct answer is the first terminal node encountered while scanning a word.

The implementation is simple:

1. Insert roots.
2. For each word, walk characters from the root.
3. If a character is missing, keep the original word.
4. If a terminal node is reached, return the prefix built so far.

The trap is continuing after finding a terminal root. If cat and cattle are both roots, cattleman should become cat, not cattle. The shortest terminal prefix wins.

Pattern 6: Word Break with trie-assisted DP

Word Break is often solved with a set and dynamic programming, but a trie can be better when the dictionary is large and many words share prefixes. Let dp[i] mean the suffix starting at index i can be segmented. For each i, walk forward through the trie until the prefix breaks. Whenever you hit a terminal word and dp[j + 1] is true, mark dp[i] true.

This avoids checking every possible substring against a set when long prefixes fail early. It also avoids creating many substring objects in languages where slicing copies memory.

The tradeoff: the trie version is more code. In an interview, use it when the prompt emphasizes many dictionary words, prefix overlap, or performance pressure. Otherwise, the set-based DP may be the clearer first solution.

Common trie mistakes that cost accepted solutions

Confusing prefix nodes with words. A node existing means a prefix exists. A terminal marker means a word exists.

Forgetting empty input behavior. Some APIs define startsWith("") as true because every word starts with an empty prefix. For LeetCode, follow the method contract; do not invent behavior mid-solution.

Overusing arrays for children. A 26-element array is fast for lowercase English letters. It is awkward for uppercase, Unicode, digits, paths, and arbitrary tokens. Use a dictionary unless the alphabet is fixed.

Not explaining space. Trie space is not simply O(n). Say O(total characters inserted) or O(number of nodes). Shared prefixes reduce actual nodes, but worst case is the sum of word lengths.

Recursive wildcard blowups. If every character is a wildcard, the search may visit many nodes. That is acceptable if bounded by dictionary size, but mention it.

Leaving found words active in grid search. If you do not clear node.word, the same word can appear multiple times in the answer.

A practical prep checklist

Before an interview, be able to code these from memory:

• A TrieNode class with children, is_end, and optional word.
• insert, search, and startsWith in under five minutes.
• Recursive wildcard search with . branching.
• Grid DFS using a trie node as the state.
• Autocomplete with sorted input and top-k suggestions stored per node.
• Complexity in terms of L, total dictionary characters, board size, and branching.

Then practice these representative problems: Implement Trie, Design Add and Search Words, Word Search II, Search Suggestions System, Replace Words, Longest Word in Dictionary, and Word Break. If you want an advanced extension, add Maximum XOR of Two Numbers using a bit trie; it uses the same prefix-tree idea on binary digits instead of letters.

How to talk about a trie in the interview

A strong verbal framing is:

"I want to avoid comparing every word against every query. Since the query is consumed left to right and a failed prefix eliminates many candidates, I’ll build a trie from the dictionary. Each DFS or query step moves one node deeper. If the next character is missing, I can stop immediately. Terminal nodes tell me when a full word has been matched."

That explanation tells the interviewer you understand the pattern, not just the code. It also sets up clean complexity analysis. For autocomplete, say the trie moves query lookup from scanning all products to walking the typed prefix. For board search, say it prunes invalid paths before exploring neighbors. For wildcard search, say it branches only over real dictionary children.

A trie is not magic. It is a way to cache shared prefixes and turn repeated string comparisons into one traversal. Use it when prefixes carry information. Avoid it when exact lookup or sorting is enough. That judgment is what makes a trie solution feel intentional instead of memorized.

Related guides

• Binary Search LeetCode Pattern Guide — Bounds, Rotated Arrays, and Search-on-Answer — A binary search LeetCode pattern guide for exact search, lower/upper bounds, rotated arrays, and search-on-answer problems. Includes invariants, templates, traps, and interview-ready explanations.
• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.
• Monotonic Stack LeetCode Pattern Guide — Next Greater Element and Histogram Problems — Learn the monotonic stack pattern for next greater element, daily temperatures, stock spans, and largest rectangle in histogram problems, with templates and interview traps.
• Topological Sort LeetCode Pattern Guide — Course Schedule and Dependency Problems — A practical topological sort LeetCode pattern guide for Course Schedule, dependency ordering, cycle detection, Kahn’s algorithm, DFS ordering, and common graph-building mistakes.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.