dsa5 min read
Tries (Prefix Trees) — Complete Guide
Master Tries: insert/search/prefix, word search II, autocomplete, XOR trie for max XOR, and bitwise trie patterns with 5-language implementations.
Read →
Prefix-tree
18 articles
dsa2 min read
Implement Trie (Prefix Tree) — Insert/Search/StartsWith
Implement a Trie with insert, search, and startsWith operations. Core data structure for all prefix-based problems.
Read →
dsa1 min read
Design Add and Search Words — Trie with Wildcard DFS
Trie that supports wildcard '.' matching any character. DFS through trie when '.' encountered, trying all children.
Read →
dsa2 min read
Word Search II — Trie + Grid DFS Pruning
Find all words from a list in a grid. Build trie from words, DFS on grid while traversing trie simultaneously to prune early.
Read →
dsa1 min read
Replace Words — Trie Shortest Prefix Replacement
Replace each word in sentence with its shortest root from dictionary. Insert roots into trie; for each sentence word find shortest matching prefix.
Read →
dsa1 min read
Search Suggestions System — Trie with Sorted Lists
After each character typed, return up to 3 lexicographically smallest matching products. Sort products, insert into trie, store sorted lists at each node.
Read →
dsa1 min read
Longest Word in Dictionary — Trie BFS/DFS
Find longest word where all prefixes exist in dictionary. Trie: only follow nodes where is_end=True, track max depth.
Read →
dsa1 min read
Palindrome Pairs — Trie + Palindrome Check
Find pairs (i,j) where words[i]+words[j] is a palindrome. Insert reversed words into trie, for each word check palindromic suffix/prefix conditions.
Read →
dsa1 min read
Stream of Characters — Reverse Suffix Trie
Query if any word ends at the current stream position. Insert reversed words into trie; maintain suffix deque to match from current position backwards.
Read →
dsa1 min read
Prefix and Suffix Search — Combined Key Trie
Find word with given prefix AND suffix. Insert 'suffix#word' for each suffix of each word into trie; query combines prefix+suffix search.
Read →
dsa1 min read
Sum of Prefix Scores of Strings — Trie Count
For each word, sum up how many other words share each of its prefixes. Trie with prefix count at each node; query each word's prefix sum.
Read →
dsa1 min read
Concatenated Words — Trie + Word Break
Find all words that can be formed by concatenating two or more words from the same list. Build trie, then run word break DP on each word.
Read →
dsa1 min read
Short Encoding of Words — Trie Suffix Dedup
Encode word list as shortest string where each word is a suffix. Words that are suffixes of others need not be separately encoded. Use trie of reversed words.
Read →
dsa1 min read
Map Sum Pairs — Trie with Value Propagation
Implement insert(key, val) and sum(prefix) returning sum of values for all keys with given prefix. Trie with value at end node.
Read →
dsa1 min read
Count Words Beginning with Prefix — Trie Count
Count words with given prefix. Simple trie with count at each node; reach prefix end and return count.
Read →
dsa1 min read
Find Length of Longest Common Prefix — Digit Trie
Find the longest common prefix length between any number in arr1 and any number in arr2. Build trie from arr1 digits, query with arr2.
Read →
dsa2 min read
Trie Applications Overview — XOR, Autocomplete, Suffix
Overview of trie application variants: binary trie for XOR, reverse trie for suffix matching, counted trie for scoring, and offline trie processing.
Read →
dsa1 min read
Count Distinct Substrings — Suffix Trie / Rolling Hash
Count distinct substrings. Naive: insert all suffixes into trie and count nodes. Optimal: suffix automaton or rolling hash.
Read →