nikunjsoni

1032

Jun 26th, 2021
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.         for(int i=0; i<26; i++)
  10.             children[i] = NULL;
  11.     }
  12.    
  13.     /** Inserts a word into the trie. */
  14.     void insert(string word) {
  15.         Trie *node = this;
  16.         for(char c: word){
  17.             c -= 'a';
  18.             if(!node->children[c])
  19.                 node->children[c] = new Trie();
  20.             node = node->children[c];
  21.         }
  22.         node->end = true;
  23.     }
  24.        
  25.     /** Returns if there is any word in the trie that starts with the given prefix. */
  26.     bool startsWith(vector<char> prefix) {
  27.         Trie *node = this;
  28.         for(char c: prefix){
  29.             c -= 'a';
  30.             if(!node->children[c])
  31.                 return false;
  32.             node = node->children[c];
  33.             if(node->end) return true;
  34.         }
  35.         return false;
  36.     }
  37. };
  38.  
  39. class StreamChecker {
  40. public:
  41.     vector<char> str;
  42.     Trie *root;
  43.     int longLen = 0;
  44.     StreamChecker(vector<string>& words) {
  45.         root = new Trie();
  46.         for(auto &word: words){
  47.             longLen = max(longLen, int(word.length()));
  48.             reverse(word.begin(), word.end());
  49.             root->insert(word);
  50.         }
  51.     }
  52.    
  53.     bool query(char letter) {
  54.         str.insert(str.begin(), letter);
  55.         if(str.size() > longLen)
  56.             str.pop_back();
  57.         if(root->startsWith(str))
  58.             return true;
  59.         return false;
  60.     }
  61. };
  62.  
  63. /**
  64.  * Your StreamChecker object will be instantiated and called as such:
  65.  * StreamChecker* obj = new StreamChecker(words);
  66.  * bool param_1 = obj->query(letter);
  67.  */
RAW Paste Data