18 articles
LeetCode 211 walkthrough — implement WordDictionary supporting add and search where the search query can contain a "." wildcard. The optimal solution combines a trie with DFS branching at every wildcard, a textbook FAANG interview pattern.
LeetCode 212 — find every dictionary word hidden in a board. The optimal solution builds a trie over the words and DFS-traverses the grid once, pruning entire branches the moment the path leaves the trie. A textbook FAANG hard problem.
LeetCode 648 — replace each word in a sentence with the shortest dictionary root that prefixes it. The trie walks one character at a time, returning the first isEnd we hit. A clean autocomplete-style problem.
LeetCode 421 — find the maximum XOR pair in an array of integers in O(N times 32) using a binary trie. The classic introduction to bit-trie pattern that powers competitive programming and database query optimisers.
LeetCode 1268 — return up to three lexicographically smallest products for every prefix of a search query. The trie autocomplete pattern that backs Google search, Amazon product search, and command palettes everywhere.
LeetCode 720 — find the longest word in a dictionary that can be built one character at a time, with each prefix also in the dictionary. Trie + BFS gives lex-smallest tie-breaking for free.
LeetCode 336 — find every pair (i,j) such that words[i] + words[j] is a palindrome. The trie solution stores reversed words and tags palindrome-suffix indices, enabling O((N times K^2)) lookup.
LeetCode 1032 — design a class that returns true whenever the suffix of a streamed character sequence matches any dictionary word. Solved with a reverse trie and a bounded sliding buffer in O(W) per query.
LeetCode 745 — design a structure that returns the highest-indexed word matching a given prefix and suffix. The combined-key trie inserts every (suffix#word) variant, turning a 2D query into a 1D trie walk.
LeetCode 2416 — for each word, sum the scores of all its non-empty prefixes where score = number of words sharing that prefix. The counted trie pattern aggregates O(N times L) work into O(N times L) trie nodes with a count counter.
LeetCode 472 — find every word that can be formed by concatenating two or more shorter words from the same list. Trie accelerates the prefix-membership test inside a Word Break DP, turning O(2^L) brute force into O(N times L^2).
LeetCode 820 — encode a list of words into the shortest reference string where each word appears as a suffix terminated by #. Build a trie of reversed words; only words at trie leaves contribute their length plus one to the answer.
LeetCode 677 — design a structure supporting insert(key, value) and sum(prefix) returning the total of values for all keys with that prefix. The key trick is propagating delta sums along the trie path so prefix queries become a single O(L) walk.
LeetCode 2185 — count how many strings in words have pref as a prefix. The simple linear scan is optimal for a single query; the trie shines once you anticipate many queries against the same word list.
LeetCode 1707 — for each query (xi, mi), find max xi XOR nums[j] where nums[j] does not exceed mi. Sort queries by mi, sort nums, insert lazily into a binary trie, answer each query in O(32). The offline-trie pattern unlocks bounded XOR queries.
LeetCode 3043 — find the longest common prefix length between any number in arr1 and any number in arr2 (compared as digit strings). A digit trie of arr1 makes each arr2 lookup O(D) where D is the number of digits.
Map of every important trie variant you need for FAANG interviews — binary trie for XOR, reverse trie for suffix matching, counted trie for prefix scoring, offline trie for bounded queries, and the design patterns that compose them.
Count the number of distinct substrings of a string. The elegant trick: every substring is a prefix of some suffix, so a suffix trie has exactly one node per distinct non-empty substring. Count nodes during insertion in O(N^2).