Introduction
Trie is a special data structure in which we store the letters of the string. It is very much helpful in finding the longest prefix, longest prefix length, searching of a particular string, finding longest word in dictionary and also for the auto complete system.
Structure
We can structure our trie based on our need. Typically we can have a char ch
denoting the character, wordEnd
which denotes while inserting the word, whether we reached the end or not, TrieNode[] array = new TrieNode[26]
which acts as a pointer which points to the index of the letter we inserted.
class TrieNode {
char ch;
TrieNode [] array = new TrieNode[26];
int wordEnd = 0;
}
So each trie node have a character, a word end and an array for pointing to the letters inserted.
We can do insert operation, search operation and many more using trie.
Insert Operation
In insert operation, we start by creating a root node, which have a wordEnd value of 0, no specific character in it and the TrieNode array.
So, suppose we are inserting a string say s = "abc"
.
We follow the below steps :
Starting from the root, we check for the index of
a
which can be found using'a' - 'a' = 0
. At first we check whether array[0] is null or not. Here array[0] is null, so from 0th index in root, we create a new trienode with a new character havinga
in it, wordEnd = 0 since the string we have to insert is not finished and the array of pointers. Now we move forward to node a.Next we have to insert
b
and this time we start from the next node, ie the node ofa
. Same as above, we find the correct index forb
using'b' - 'a' = 1
. Here we check whether array[1] is null or not, if it is null, then a new node forb
is created as above with the respective field, otherwise it denotes that we already insertedb
and we continue with the next node. In our exampleabc
, a new node forb
will be created. Now we move forward to node b.
Note : The wordEnd will be still 0, as we are not finished with our string.Next we insert
c
by finding the index'c' - 'a' = 2
. We check whether array[2] is null or not, here it will be null so a new node will be generated forc
node.
Here we are finished with the string, so the wordEnd value will be updated towordEnd = wordEnd + 1
.
Let's continue inserting another string s = "abd"
Here again we start from the root, and find the index for the first character, ie a here, which is
'a' - 'a' = 0
. So here array[0] is not null, as we already inserted it before, so we continue into the nodea
without creating a new node.Next we have to insert
b
. Finding the index forb
which is'b' - 'a' = 1
. Here also while we check array[1] null or not from node a, we can see it is already inserted, so without creating a new node, we move forward to node b.Next character is
d
and we find the index ford
which is'd' - 'a' = 3
. If we check array[3] == null, we can see it is null, and therefore a new node is created ford
.
Sinced
is the last character of the string, we increment thewordEnd
towordEnd + 1
to indicate we are finished with the stringabd
.
Let's insert one more string s = "bcd"
.
Same as above procedure, let's do it once more.
Start from the root, find the index of the first character
b
which'b' - 'a' = 1
and its value in array[1] is null, so a new node for b is created and we move forward to node b.Next character is
c
and its index ='c' - 'a' = 2
. From node b, if we look for the value of array[2], we get it is null and we create a new node forc
and continue with that node.Next character is
d
and its index ='d' - 'a' = 3
. From node c, if we look for the value of array[3], we get it is null and a new node is created. Since d is the last character of the string, we increment the wordEnd bywordEnd + 1
.
The final structure of the trie after these insertion will be :
Time Complexity :
O(number of words * maxLengthOfWord)
Space Complexity :
O(number of words * maxLengthOfWord)
Code :
class TrieNode {
char ch;
TrieNode [] array = new TrieNode[26];
int wordEnd = 0;
}
public class Trie {
TrieNode root = null;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (node.array[index] == null) {
node.array[index] = new TrieNode();
node.array[index].ch = ch;
node.array[index].wordEnd = 0;
}
node = node.array[index];
}
node.wordEnd += 1;
}
public static void main(String [] args) {
Trie trie = new Trie();
String a = "abc";
String b = "abd";
String c = "bcd";
trie.insert(a);
trie.insert(b);
trie.insert(c);
}
}
Resources for trie :
Rohithv07 / LeetCodeTopInterviewQuestions
Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions
LeetCodeTopInterviewQuestions
Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions-easy/
Also Question answered from CodeSignal.com : https://app.codesignal.com/
This video is a great one to know about trie.
Top comments (0)