Tries — prefix search and autocomplete
A tree keyed by character. Autocomplete, spellcheck, and IP routing tables all live here.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
One node per character
A trie (pronounced 'try') stores strings by walking one character per node. Each edge is a character; each root-to-node path spells a prefix. The end flag marks nodes where a stored word terminates. Lookup cost depends only on the query length, never on the number of stored words.
Insert, contains, prefix
insert(word) walks down from the root, creating nodes as needed, and flips end = true at the last one. contains(word) walks the same path and returns end. startsWith(prefix) walks the prefix and returns true if the walk didn't hit a dead end — it doesn't care whether the prefix itself is a stored word.
Autocomplete
Walk to the prefix node, then DFS from there collecting every descendant that has end = true. Rank the results by frequency or recency to build a real autocomplete feature. The trie handles the search space pruning; ranking is your business logic.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Memory vs speed
A HashMap per node is flexible but heavy. For a small fixed alphabet (say lowercase a–z), swap it for a Node[26] — faster and smaller. For very large dictionaries, look up compressed tries (radix trees) or DAWGs (directed acyclic word graphs), which share suffixes across words.
Beyond words
Tries generalize to any sequence of tokens. IP routers use tries over bits for longest-prefix matching. Filesystems use them over path segments. Anywhere you need prefix queries on a large alphabet, the trie is the right shape.