Tries
Sharing the prefix
A tree where the path spells the word. Two fields per node and that is the whole structure.
Key idea
The question a set cannot answer
A set of words answers is this exact word present in constant time. It cannot answer does any word start with this, without checking every word.
A trie answers both. Words are stored as paths through a tree, one character per edge, so every word sharing a prefix shares the path for that prefix. Asking about a prefix is then just walking that path.
Key idea
Two fields per node
Each node holds a map from the next character to the child node, and a flag saying whether a word ends here.
That flag is essential and easy to forget. Without it there is no way to tell a complete word from a prefix of a longer one, so a trie holding cart would claim to hold car.
Why it works
Searching is one walk, and the two questions differ by one line
To find either a word or a prefix, walk from the root following one character at a time. Failing to find a child means neither exists.
Reaching the end of the input successfully means the prefix exists. Whether a word exists is then a single extra check of the flag on the node you landed on.
Following the same trie by hand makes the difference between the two answers concrete. Both walks below succeed; only one of them lands on a flag.
Tip
`setdefault` collapses the insert
Insertion is the mirror of that walk: follow the characters, and create a node whenever the next one is missing. Written plainly that is a check, a create, and a descend.
node.children.setdefault(ch, Node()) does all three in one expression, returning the existing child if there is one and installing a new one otherwise. One caveat: the Node() is constructed on every call whether or not it gets used, which is wasteful but harmless here. When constructing the default is expensive, the explicit branch is better.
Key idea
A dict of children, not an array
Some presentations use a fixed array of 26 slots per node. That is faster and assumes a known small alphabet, and it wastes space on sparse tries.
A dict handles any alphabet and only stores the branches that exist. Use the dict unless the problem promises lowercase English letters and asks about memory, in which case mention the array as the alternative.
Cost
What a trie costs
Adding or finding a word of length L is O(L), independent of how many words the trie holds. That is the headline: lookup does not slow down as the dictionary grows.
Space is O(total characters) in the worst case, and much less when prefixes are shared, which is the whole point. Compare with a set of n words, which is O(1) average lookup for exact matches and no help at all for prefixes.
Predict the output: the missing flag
This trie has no end-of-word flag and treats any successful walk as a word. Type the three values it prints.
Reading a trie that already exists
A trie is given as nested dictionaries, where a # key marks the end of a stored word. count_words reports how many words the whole trie holds. count_with_prefix reports how many of them begin with a given prefix. longest_stored_prefix_of returns the longest stored word that is a prefix of the given text, or the empty string if there is none.
Tests
print(count_words(TRIE), count_words({}))
print(count_with_prefix(TRIE, "ca"), count_with_prefix(TRIE, "do"), count_with_prefix(TRIE, "z"), count_with_prefix(TRIE, ""))
print(longest_stored_prefix_of(TRIE, "cartoon"), longest_stored_prefix_of(TRIE, "carbon"), repr(longest_stored_prefix_of(TRIE, "zebra")))Output
Run the tests when you are ready.
Implement Trie Prefix Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.