How to Implement Trie (Prefix Tree) - Blind 75 LeetCode Questions by@rakhmedovrs

How to Implement Trie (Prefix Tree) - Blind 75 LeetCode Questions

July 24th 2022 11,733 reads

Trending #11

Read on Terminal Reader
Open TLDR
react to story with heart
react to story with light
react to story with boat
react to story with money
Trie is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. The Trie data structure is the classic data structure that is widely used in text searching. We need to implement Trie with the following method: Trie() and Trie.insert(). In the real example of Trie we had to introduce a small part of the data structure which consists of smaller pieces called **Tree. nodes.
image
Ruslan Rakhmedov HackerNoon profile picture

Ruslan Rakhmedov

Software Engineer, Stripe


Task description:

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.


Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.


Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True


Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.


Reasoning:

Trie is the classic data structure that is widely used. One of the most famous uses is text searching. Let’s take Google.com as an example.


image


Google’s example

Have you ever noticed whenever you start typing a search phrase to a search bar you almost immediately get some suggestion from the searching system? I bet the answer is “Yes”. The Trie data structure makes it possible.


Let’s add some words to Trie and see how it looks like this:


image

Example of Trie with some words

The Trie above contains words: Algorithm, Animation, Ant, Apache, Append, Apple, Application, Apricot. As you may notice we treat every word as a sequence of characters.


Starting from the first character of each word we attach it to the root of the Trie and move down till we reach the last character of each word.


Once we reached the end of a word we mark that last Node as the end of the word. I hope now it’s clear to you how it works in general. If you still struggle with it, I recommend you to read Wikipedia’s article.


Solution:

We are to implement Trie with the following method:



As we saw in the example of real Trie we had to notice that as with any other Tree data structure it consists of smaller pieces which are usually called Node. Let’s introduce this small part:



A few things we need to have a closer look at here:

We have the chars boolean array which will tell us if we have particular characters in a particular node. isEnd boolean variable which answers just one question, whether or not the current node is the end of a word in our Trie. Last but not least children TrieNode array stores child TrieNodes of the current TrieNode.


Let’s look at other methods, one by one:


Method void insert(String word)returns nothing and accepts word to insert into the Trie:



Starting from the root of the Trie we iterate through every char in provided word and create a new TrieNode every time if we don’t have one. At the last character in word, we mark TrieNode as isEnd.



The next method in our list is boolean search(String word) which searches for a particular word in the Trie and returns a boolean value depending on whether or not the Trie contains it. As input, it takes a word.



Here we do the same as in the previous method except for a few things. Iterate through every character in provided word and if we don’t have a child with the next character we return false. At the end of a word, we return the current node value of isEnd.



Lastly method boolean startsWith(String prefix)takes prefix and returns true if we have a prefix in our Trie if not we return false.



This method does completely the same as the previous one except for only one thing. If we managed to iterate through the whole prefix we return true, because we’re looking for the prefix and not an entire word, otherwise we return false.


As always at the end of the article, I prove the full source code of the problem



It has linear time and space complexity and has the following position among other people's solutions.


Submission detail

Submission detail



Also published here.

react to story with heart
react to story with light
react to story with boat
react to story with money
L O A D I N G
. . . comments & more!