#include<bits/stdc++.h>
using namespace std;

class Trie{
    private:
    static const int chars =26;
    Trie* child[chars];
    bool isLeaf {};

    public:
    
    Trie(){
        memset(child,0,sizeof(child));
    }
    
    void insert(string s ,int idx){
    	
        if(idx == s.length()){
            isLeaf =true;
        }
        
        else{
            int cur = s[idx]-'a';
            if(child[cur] == nullptr){
                child[cur] = new Trie();
            }
            child[cur]->insert(s,idx+1);
        }
    }
    
    bool wordExit(string s,int idx){
        if(idx == s.size()) return isLeaf;
        int cur = s[idx]-'a';
        if(!child[cur]) return false;
        return child[cur]->wordExit(s,idx+1);
    }
    
    bool prefixExit(string s,int idx){
        if(idx == s.size()) return true;
        int cur = s[idx]-'a';
        if(!child[cur]) return false;
        return child[cur]->prefixExit(s,idx+1);
    }
    
    //Problem 3 : home work 2
    bool findAfter(string s,int idx){
        for(int i=0;i<s.length();i++){
            char c = s[i];
            for(char j='a';j<='z';j++){
                if(j!=c){
                    s[i]=j;
                    if(wordExit(s,0)){
                        return true;
                    }
                }
            }
            s[i]=c;
        }
        return false;
    }
    
};
int main(){
    Trie trie;
    trie.insert("hello",0);
    trie.insert("world",0);
    
    cout << boolalpha << trie.findAfter("heldo",0)<<endl;
    cout <<boolalpha<< trie.findAfter("worsd",0)<<endl;
    cout <<boolalpha<<trie.findAfter("hello",0)<<endl;
    cout <<boolalpha<<trie.findAfter("manar",0)<<endl;
    return 0;
}