Trie
Store the words letter by letter, one node per prefix, so a shared prefix is stored once. A walk of L steps then answers both “is this a word?” and “does any word start with this?”, however many words there are.
Problems worked on this page, and more to practise
- 208. Implement Trie (Prefix Tree)
- 211. Design Add and Search Words Data Structure
- 212. Word Search II
- 14. Longest Common Prefix
- 720. Longest Word in Dictionary
- 648. Replace Words
- 677. Map Sum Pairs
- 1268. Search Suggestions System
- 139. Word Break
- 421. Maximum XOR of Two Numbers in an Array
- 745. Prefix and Suffix Search
- 336. Palindrome Pairs
When should I use a trie instead of a hash set?
Only when a question you have to answer is about a prefix. A hash set answers “was this exact word stored?” in one probe, and a trie is more code and more memory for the same answer. A trie earns its place when you also need “does any stored word start with this?”, the list of words under a prefix, or a search that has to stop as soon as no word can continue, as in Word Search II. If no prefix appears in the question, use a set.
What is the difference between search and startsWith in a trie?
One line. Both follow the same path down from the root, one node per character, and both fail the moment a character has no child. The difference is what happens when the path runs out: startsWith answers true because arriving is enough, while search also reads the end-of-word flag on the node it arrived at. Without that flag, inserting “apple” would make search("app") answer true, because the node for “app” exists on the way to “apple”.
How much memory does a trie use?
One node per distinct prefix, so the worst case is one node per character of every word, and the best case is far less when the words share prefixes. Storing app, apple, apply, ape, apt and bat takes 22 characters and 11 nodes, because the six words share a great deal of their fronts. Each node also carries a dict of children, and a dict costs far more per entry than a character, so a trie usually uses more memory than the list of strings it replaces.
Why is a trie faster than scanning a list of words?
Because the number of stored words appears nowhere in the walk. Answering a prefix query against a list compares the query with every word, which costs the length of the query times the number of words. A trie reads each character of the query once and looks it up in a dict, so the cost is the length of the query and nothing else. Doubling the dictionary doubles the scan and leaves the trie untouched.
Why does Word Search II build a trie of the words?
Because a trie turns the search over the word list into a search that prunes. Running Word Search once per word restarts a grid DFS for every word, and there can be thirty thousand of them. With a trie, one DFS from each cell carries the current trie node alongside the current cell: when the node has no child for the next letter, no word in the whole list can continue that way, and the branch is abandoned there and then.