nikunjsoni

208

Jun 25th, 2021 (edited)
90
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Trie {
  2. private:
  3.     bool end;
  4.     Trie* children[26];
  5. public:
  6.     /** Initialize your data structure here. */
  7.     Trie() {
  8.         end = false;
  9.         memset(children, NULL, sizeof children);
  10.     }
  11.    
  12.     /** Inserts a word into the trie. */
  13.     void insert(string word) {
  14.         Trie *node = this;
  15.         for(char c: word){
  16.             c -= 'a';
  17.             if(!node->children[c])
  18.                 node->children[c] = new Trie();
  19.             node = node->children[c];
  20.         }
  21.         node->end = true;
  22.     }
  23.    
  24.     /** Returns if the word is in the trie. */
  25.     bool search(string word) {
  26.         Trie *node = this;
  27.         for(char c: word){
  28.             c -= 'a';
  29.             if(!node->children[c])
  30.                 return false;
  31.             node = node->children[c];
  32.         }
  33.         return node->end;
  34.     }
  35.    
  36.     /** Returns if there is any word in the trie that starts with the given prefix. */
  37.     bool startsWith(string prefix) {
  38.         Trie *node = this;
  39.         for(char c: prefix){
  40.             c -= 'a';
  41.             if(!node->children[c])
  42.                 return false;
  43.             node = node->children[c];
  44.         }
  45.         return true;
  46.     }
  47. };
  48.  
  49. /**
  50.  * Your Trie object will be instantiated and called as such:
  51.  * Trie* obj = new Trie();
  52.  * obj->insert(word);
  53.  * bool param_2 = obj->search(word);
  54.  * bool param_3 = obj->startsWith(prefix);
  55.  */
RAW Paste Data