class Trie {

     bool isWord;

     vector<Trie*> children;

 public:

     /** Initialize your data structure here. */

     Trie() {

         isWord=false;

         children.assign(,nullptr);

     }

     /** Inserts a word into the trie. */

     void insert(string word) {

         if(word.empty()){return;}

         auto cur=this;

         for(int i=;i<word.size();++i){

             if(cur->children[word[i]-'a']==nullptr){

                 cur->children[word[i]-'a']=new Trie();

             }

             cur=cur->children[word[i]-'a'];

         }

         cur->isWord=true;

     }

     /** Returns if the word is in the trie. */

     bool search(string word) {

         auto cur=this;

         for(int i=;i<word.size();++i){

             if(cur->children[word[i]-'a']==nullptr){

                 return false;

             }

             cur=cur->children[word[i]-'a'];

         }

         return cur->isWord;

     }

     /** Returns if there is any word in the trie that starts with the given prefix. */

     bool startsWith(string prefix) {

         auto cur=this;

         for(int i=;i<prefix.size();++i){

             if(cur->children[prefix[i]-'a']==nullptr){

                 return false;

             }

             cur=cur->children[prefix[i]-'a'];

         }

         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);

  */