Trie is an advanced data structure used to store strings so that we can search the string in O(N) time complexity, where N is the maximum length of a string. The concept behind a trie is to store strings in a tree structure where each node has 26 child nodes, each representing a character of the alphabet. In this article, we will discuss the problem “Implement Trie”.
How to Implement Trie?
Trie is a special type of tree in which each node has 26 child nodes. Trie is used to store strings in a tree so that we can find them in O(N) time complexity.
To implement a Trie, we will create a class called Node. Each node in this class will contain 26 characters and a Boolean variable, ‘flag’, indicating whether any string ends at this node. If the boolean value is true, it means a string ends at this node. If it is false, it means this node represents a substring of another string. Now, we will iterate over each string and store it in the trie.
Let’s examine this process step by step.
- First, create a class having a list of 26 characters and a boolean variable flag whose initial value is false.
- Now iterate over the array if it is inserted, then call the insert function; otherwise, call the search function.
- To create an insert function, you need an input string and the root of the tree. Now, iterate through the whole string and call the list for that character. For example, if you want to store “bat”, then first call the “b” in the root node and update the current node with the “b” node. Now store the “a” in the current node and update the current node with the “a” node. Finally, call the “t” node in the current node and mark its flag as true.
- To create a search function, you need the input string and the root node of the tree. Now, iterate through the entire string as we have done in the insert function. The only change in this function is to check for the last character to determine if the flag value is true or not. If it’s true, it means the string lies inside the array; otherwise, it does not. Additionally, if any character is not within the string, return false.
Let’s examine the code for Implement Trie Problem.
C++ Code:
#include<bits/stdc++.h>
using namespace std;
class Node{
public:
Node* list[26];
bool flag=false;
bool key(char ch){
if(list[ch-'a']==NULL) return false;
return true;
}
void put(char ch){
list[ch-'a']=new Node();
return;
}
};
Node* root = new Node();
void insert(string word) {
Node* curr=root;
for(int i=0;i<word.size();i++){
if(!(curr->key(word[i]))){
curr->put(word[i]);
}
curr=curr->list[word[i]-'a'];
}
curr->flag=true;
return;
}
bool search(string word) {
Node* curr=root;
for(int i=0; i<word.size();i++){
if(!(curr->key(word[i]))){
return false;
}
curr=curr->list[word[i]-'a'];
}
return curr->flag;
}
int main(){
vector<string> v = {"ant", "an", "app", "ban", "bat", "bell"};
vector<string> s = { "ap", "apple", "ban", "bell"};
for(int i=0; I <v.size(); i++){
insert(v[i]);
}
for(int i=0; i< s.size(); i++){
(search(s[i]))? cout<<"True"<<endl:cout<<"False"<<endl;
}
return 0;
}Java Code:
import java.util.*;
class Trie {
static class Node {
Node[] list = new Node[26];
boolean flag = false;
boolean key(char ch) {
return list[ch - 'a'] != null;
}
void put(char ch) {
list[ch - 'a'] = new Node();
}
}
static Node root = new Node();
static void insert(String word) {
Node curr = root;
for (int i = 0; i < word.length(); i++) {
if (!curr.key(word.charAt(i))) {
curr.put(word.charAt(i));
}
curr = curr.list[word.charAt(i) - 'a'];
}
curr.flag = true;
}
static boolean search(String word) {
Node curr = root;
for (int i = 0; i < word.length(); i++) {
if (!curr.key(word.charAt(i))) {
return false;
}
curr = curr.list[word.charAt(i) - 'a'];
}
return curr.flag;
}
public static void main(String[] args) {
List<String> v = Arrays.asList("ant", "an", "app", "ban", "bat", "bell");
List<String> s = Arrays.asList("ap", "apple", "ban", "bell");
for (String word : v) {
insert(word);
}
for (String word : s) {
System.out.println(search(word) ? "True" : "False");
}
}
}Python Code:
class Trie:
class Node:
def __init__(self):
self.list = [None] * 26
self.flag = False
def key(self, ch):
return self.list[ord(ch) - ord('a')] is not None
def put(self, ch):
self.list[ord(ch) - ord('a')] = Trie.Node()
root = Node()
@staticmethod
def insert(word):
curr = Trie.root
for ch in word:
if not curr.key(ch):
curr.put(ch)
curr = curr.list[ord(ch) - ord('a')]
curr.flag = True
@staticmethod
def search(word):
curr = Trie.root
for ch in word:
if not curr.key(ch):
return False
curr = curr.list[ord(ch) - ord('a')]
return curr.flag
v = ["ant", "an", "app", "ban", "bat", "bell"]
s = ["ap", "apple", "ban", "bell"]
for word in v:
Trie.insert(word)
for word in s:
print("True" if Trie.search(word) else "False")Output:
False
False
True
TrueAdvantages of Trie:
- Trie reduces the time to search a string or substring of any string to O(N) time complexity. Where N is the size of the longest string.
- It takes less space when we contain a large number of short strings.
- It can easily solve questions like “Replace Words,” “Design Search Autocomplete System,” etc.
The insertion operation takes O(N), where N is the size of each string. The space complexity for the insertion function is O(M*N) where M is the total number of times the insertion function is called.
The search operation takes O(N) time complexity. The space complexity for the search function is O(1) as we are not using any space during the search operation.
So, the overall time complexity is O(n), and the space complexity is O(n*m).
Conclusion
In this article, we have seen how to implement a trie. If we used a hash map in place of a trie, we might use less space to store the strings and also less time to search for the string. However, the hash map is not as useful when we are searching for substrings, which can easily be found by a trie.
