Tuesday, 6 December 2016

checking existance of a string in a dictonarty and adding a word in dictonary

// code for checking existance of a string in a dictonarty and adding a word in dictonary
#include<bits/stdc++.h>
using namespace std;
class node
{
public :
node *pointers[26];
int end;

node()
{
for(int i=0;i<27;i++)
{
pointers[i]=NULL;
}
end=0;
}

};
void add(node *curr,string s)
 {
  int len=s.length();
  for(int i=0;i<len;i++)
    {
      int  idx=s[i]-'a';
       if(curr->pointers[idx]!=NULL)
         {
  curr=curr->pointers[idx];
     
 }
 else
 {
  curr->pointers[idx]=new node();
 curr=curr->pointers[idx];
 }
    if(i==len-1) curr->end+=1;
  }
 }

bool check(node * curr,string s)
 {
  int len=s.length();
  for(int i=0;i<len;i++)
    {
      int  idx=s[i]-'a';
    if(curr->pointers[idx]!=NULL)
         {
  curr=curr->pointers[idx];
     
 }
 else
 {
   return false;
 }
 if(i==len-1) return (curr->end >=1);
   
  }
  return true;
 }

int main()
 {
  cout<<" give the number of opetrations "<<endl;
  node * root =new node();
  int    count =0;
  cin>>count;
  while(count)
   {
     int type;
       cout<<" for adding a string press 0 \n for checking press 1  "<<endl;
      cin>>type;
   
      if(type==0)// add;
          {
   string s;
cin>>s;  
 if(!check(root,s))
 {
  add(root,s);
 }
 else
 {
  cout<<"already exists :)"<<endl;
 }
   }
 
   else if(type==1)
   {
    string ss;
    cin>>ss;
    if(check(root,ss))
     {
      cout<<" existes "<<endl;
 }
 else
 {
  cout<<" not exists "<<endl;
 }
}
else
{
cout<<"invalid type "<<endl;
}
 
 }
 }