fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Trie{
  5.     private:
  6.     static const int chars =26;
  7.     Trie* child[chars];
  8.     bool isLeaf {};
  9.  
  10.     public:
  11.  
  12.     Trie(){
  13.         memset(child,0,sizeof(child));
  14.     }
  15.  
  16.     void insert(string s ,int idx){
  17.  
  18.         if(idx == s.length()){
  19.             isLeaf =true;
  20.         }
  21.  
  22.         else{
  23.             int cur = s[idx]-'a';
  24.             if(child[cur] == nullptr){
  25.                 child[cur] = new Trie();
  26.             }
  27.             child[cur]->insert(s,idx+1);
  28.         }
  29.     }
  30.  
  31.     bool wordExit(string s,int idx){
  32.         if(idx == s.size()) return isLeaf;
  33.         int cur = s[idx]-'a';
  34.         if(!child[cur]) return false;
  35.         return child[cur]->wordExit(s,idx+1);
  36.     }
  37.  
  38.     bool prefixExit(string s,int idx){
  39.         if(idx == s.size()) return true;
  40.         int cur = s[idx]-'a';
  41.         if(!child[cur]) return false;
  42.         return child[cur]->prefixExit(s,idx+1);
  43.     }
  44.  
  45.     //Problem 3 : home work 2
  46.     bool findAfter(string s,int idx){
  47.         for(int i=0;i<s.length();i++){
  48.             char c = s[i];
  49.             for(char j='a';j<='z';j++){
  50.                 if(j!=c){
  51.                     s[i]=j;
  52.                     if(wordExit(s,0)){
  53.                         return true;
  54.                     }
  55.                 }
  56.             }
  57.             s[i]=c;
  58.         }
  59.         return false;
  60.     }
  61.  
  62. };
  63. int main(){
  64.     Trie trie;
  65.     trie.insert("hello",0);
  66.     trie.insert("world",0);
  67.  
  68.     cout << boolalpha << trie.findAfter("heldo",0)<<endl;
  69.     cout <<boolalpha<< trie.findAfter("worsd",0)<<endl;
  70.     cout <<boolalpha<<trie.findAfter("hello",0)<<endl;
  71.     cout <<boolalpha<<trie.findAfter("manar",0)<<endl;
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
true
false
false
https://ideone.com/QH5pex
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!