A trie is a tree where each edge is labeled with a character. A node represents the string formed by concatenating edge labels on the path from the root. Insert, lookup, and prefix queries take time, where is the length of the string — independent of how many strings the trie holds.
Use case: autocomplete
Store all dictionary words in a trie. To autocomplete "compu", walk down the path "c" → "o" → "m" → "p" → "u", then DFS from that node to collect every word starting with "compu." The number of nodes visited is proportional to the number and length of matching words, not to the dictionary size.
Storage
Two common layouts. Array per node: each node holds an array of 26 (or 256) children — space per node. Hash map per node: each node holds a map from character to child — slower constant but uses memory only for branches that exist. For English-language autocomplete, the map version is usually preferred.
Word break
"Given a string and a dictionary, can the string be segmented into dictionary words?" — load the dictionary into a trie and do DP over string prefixes, walking the trie one character at a time. time, very tight constant.
Suffix trees / arrays
Generalizations of tries used for sophisticated string matching. Suffix arrays are easier to implement and almost as powerful; they're the backbone of high-performance text search.
When you SHOULDN'T use a trie
When all you need is exact-match lookup, a hash set is faster and simpler. When the alphabet is huge (Unicode), the per-node array becomes wasteful — switch to hash-map children. When memory is tight and prefixes are long, tries can balloon — radix tries (which compress chains of single-child nodes) help.