Tries let you quickly check whether a word you've seen starts with a string. For example, if you have words "pizza", "zap", and "pie", you can create a Trie like this:

You can quickly check if any of the words starts with "pi" - you first follow the "p" and then the "i", and you end up at a node, which means that one of the words starts with a "pi". In general, to check if any of the words starts with a string, you simply walk down the Trie.

Searching through a Trie is very fast because all the words are combined together, so you don't have to loop over the words individually.

One easy way to create a Trie is to nest many HashMaps, like this * :

Right now, the trie gets rid of some information about the words you're storing. For example, there's no way to tell if you added the word "pi" to the trie, or if you didn't add "pi" and it only shows up in the trie because "pi" is a prefix to the word "pizza".

If you care about keeping track of the specific words you've added, you need to store a little extra information. You can either store a Set containing all the words you've added, or you can keep track of all the nodes in the trie that end a word you've added - either way has the same lookup time complexity, so it doesn't matter which you pick. Here's what people usually do:

We'll practice implementing and traversing a trie in the next problem.