We're going to be implementing a Trie to solve this problem, since Tries give us fast prefix lookups. See the previous lesson for details, but the main idea is to turn the strings we've seen into a Trie like this:

We saw that one easy way to create a Trie is to nest many nested HashMaps. This is how we'll implement our Trie:

To add a string to the Trie, we can walk letter by letter in the string and making sure there's a node for each letter. If there's not a node, we'll add one in.

To find if a prefix is in the Trie, we can walk letter-by-letter, making sure there's a node for each letter.

To find if an entire string is in the Trie, we can use the same exact code as above. The only difference is we have to check whether the node we end up on is the end to one of the words we've seen. Here's the code for this:

To code this up, we can combine all of these methods. The initialization function needs to set up the Trie right by storing the root node of the tree root (an empty HashMap at the start). Here's the full code:

add Complexity: $O(m)$, where $m$ is the length of the inserted string.

hasPrefix Complexity: $O(m)$

has Complexity: $O(1)$

init Complexity: $O(1)$