#include<bits/stdc++.h>
using namespace std;
class Node
{
public:
char data;
unordered_map<char,Node*> children;//this is a hashmap that stores the pointer to each chilren of curent node
bool terminal;//this variable is used to tell whether this node is last letter of the word or not
Node(char d)
{
data=d;
terminal=false;//initially we keep all the nodes as non-terminal
}
};
class Trie
{
Node * root; //pointer to root node
public:
Trie()
{
root=new Node('\0');//making a root node and initializing it with NULL
}
void insert(char *w)//we received a character array(word)
{
Node * temp=root;
for(int i=0;w[i]!='\0';i++)//iterating through the whole word
{
char ch=w[i];
if(temp->children.count(ch))//this means that the ith letter of the word is already present in the trie
{
temp=temp->children[ch];//we just update the temp pointer to point to that letter's node
}
else//this means that the letter node is not present in the trie yet
{
Node * n=new Node(ch);//so we create the new node with data ch
temp->children[ch]=n; //updating the children hashmap of temp with ch->n
temp=n;//updating our temp t point to newly created node
}
}
temp->terminal=true;// once the whole word is inserted then our temmp willl point towards the last letter of inserted word so we make terminal value of that letter as true so that we know that this word is ending at this character
}
bool search(char * w)
{
Node * temp=root;
for(int i=0;w[i]!='\0';i++)
{
char ch=w[i];
if(temp->children.count(ch)==0) //this means that the current letter of word in not present in the Trie so word is also not present
{
return false; //we return false
}
else//this means that the current letter of given word is present
{
temp=temp->children[ch];//we move our temp pointer to current letter node do that we can search for next letters
}
}
if(temp->terminal==true)//after iterating through complete word our temp will be pointing to the last letter of the word we are sarching so we will return true only if the last letter's node is terminal node otherwise our word to be searched can be a prefix to other word.Ex:- the is the word to be searched but in our trie we have a word them where m is the terminal node, although the is present in them but not as a word but as a prefix so we return false
{
return true;
}
else
{
return false;
}
}
void Remove(char *w)
{
Node * temp=root;
for(int i=0;w[i]!='\0';i++)
{
char ch=w[i];
if(temp->children.count(ch)==0)//if the letter of given word is not present in our trie then we can't delete is so we just return
{
return ;
}
else//if the letter is present the we just move our temop pointer to next letter's node
{
temp=temp->children[ch];
}
}
temp->terminal=false;//now we are at the last node of the given word so we just make it's terminal value as false, and this word can't be find in Trie as it does not have it's last letter marked as terminal
}
};
int main()
{
Trie T;
char words[][10]={"Deep","Aashi","Sanjay","Sushma"};
for(int i=0;i<4;i++)
{
T.insert(words[i]);
}
cout<<T.search("Deep")<<endl;
T.Remove("Deep");
cout<<T.search("Deep")<<endl;
return 0;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}