LeetCode · Trie
Trie Problem Set
Prefix trees, wildcard search, trie + DFS, bitwise tries for XOR, and ranking-driven autocomplete design. If the problem says “prefix”, “starts with”, or “maximum XOR”, trie should be on your shortlist.
Concept page: Trie
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | trie | LC 208 · Implement Trie (Prefix Tree) | Build the core API: insert, exact search, and startsWith. The key distinction is that search checks isEnd, while startsWith only checks path existence. |
| Medium | trie + dfs | LC 211 · Design Add and Search Words | Standard insert, but search must branch on '.' by trying every child. This turns query into DFS over trie states. |
| Hard | dfs + trie | LC 212 · Word Search II | Build a trie from the dictionary, then DFS the board while walking trie nodes at the same time. The trie prunes dead prefixes immediately. |
| Medium | bitwise trie | LC 421 · Maximum XOR of Two Numbers in an Array | Insert integers bit by bit from MSB to LSB. To maximize XOR, greedily prefer the opposite bit at each level if it exists. |
| Medium | trie | LC 648 · Replace Words | Insert every root word, then scan each sentence word until the first terminal node appears. Earliest terminal prefix gives the shortest replacement root. |
| Hard | trie + ranking | LC 642 · Design Search Autocomplete System | Navigate to the prefix node, gather candidate sentences from the subtree, and rank them by frequency and lexicographic order. |
Practice note: This page is the canonical trie problem set for the topic page. The associated trie solution write-ups have not been added under
/tech/dsa/leetcode/solutions/ yet, so these entries are intentionally kept as a clean practice list rather than dead links.