Untitled

class Node{
    public:
    bool is_word;
    Node* child[26]; //an array named child containing 26 pointers to its chdild nodes
    Node(){//constructor
        is_word=false;
        for(int i=0;i<26;i++){
            child[i]=NULL;
        }
    }
};



class Trie {
public:
    Node* root;
    Trie() {
        root= new Node();
    }
    
    void insert(string word) {
        int k=0;
        Node* cur=root;
        for(int i=0;i<word.size();i++){    
            k=word[i]-'a';

            if(cur->child[k]==NULL){
                cur->child[k]=new Node(); //we dont set any value to the node created , we just store the pointer of the node created to the child array at index k and check if a node exists or not
            }
            cur=cur->child[k];
        }
        cur->is_word=true;
    }
    
    bool search(string word) {
        int k=0;
        Node* cur=root;
        for(int i=0;i<word.size();i++){
            int k=word[i]-'a';
            if(cur->child[k]==NULL) return false;
            cur=cur->child[k];
        }
        return cur->is_word;
    }
    
    bool startsWith(string prefix) {
        int k=0;
        Node* cur=root;
        for(int i=0;i<prefix.size();i++){
            k=prefix[i]-'a';
            if(cur->child[k]==NULL) return false;
            cur=cur->child[k];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */