nikunjsoni

211

Jun 25th, 2021
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class TrieNode {
  2. public:
  3.     bool end;
  4.     TrieNode* children[26];
  5.     TrieNode() {
  6.         end = false;
  7.         for(int i=0; i<26; i++)
  8.             children[i] = NULL;
  9.     }
  10. };
  11.  
  12. class WordDictionary {
  13. public:
  14.     /** Initialize your data structure here. */
  15.     WordDictionary() {
  16.        
  17.     }
  18.    
  19.     /** Adds a word into the data structure. */
  20.     void addWord(string word) {
  21.         TrieNode* node = root;
  22.         for(char c : word) {
  23.             c -= 'a';
  24.             if(!node->children[c]) {
  25.                 node->children[c] = new TrieNode();
  26.             }
  27.             node = node->children[c];
  28.         }
  29.         node->end = true;
  30.     }
  31.    
  32.     /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
  33.     bool search(string word) {
  34.         return search(word.c_str(), root);
  35.     }
  36.    
  37. private:
  38.     TrieNode* root = new TrieNode();
  39.    
  40.     bool search(const char* word, TrieNode* node) {
  41.         for(int i = 0; word[i] && node; i++) {
  42.             if(word[i] != '.') {
  43.                 node = node->children[word[i] - 'a'];
  44.             } else {
  45.                 TrieNode* tmp = node;
  46.                 for(int j = 0; j < 26; j++) {
  47.                     node = tmp->children[j];
  48.                     if(search(word + i + 1, node)) {
  49.                         return true;
  50.                     }
  51.                 }
  52.             }
  53.         }
  54.         return node && node->end;
  55.     }
  56. };
RAW Paste Data