text: //https://leetcode.com/problems/add-and-search-word-data-structure-design/
  class WordDictionary {
  public:
      WordDictionary() {}
      
      void addWord(string word) {
          words[word.size()].push_back(word);
      }
      
      bool search(string word) {
          for(auto s: words[word.size()]) if(isEqual(s, word)) return true;
          return false;
      }
      
  private:
      unordered_map<int, vector<string>>words;
      
      bool isEqual(string a, string b){
          for(int i = 0; i < a.size(); i++){
              if(b[i] == '.') continue;
              if(a[i] != b[i]) return false;
          }
          return true;
      }
  };
  
  // Method 2: Trie
  struct TrieNode{
      bool isKey;
      TrieNode* next[26];
      TrieNode():isKey(false){
          memset(next, NULL, sizeof(next));
      }
  };
  
  class WordDictionary {
  public:
      WordDictionary() {
          root = new TrieNode();
      }
      
      void addWord(string word) {
          TrieNode* node = root;
          for(auto c: word){
              if(!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
              node = node->next[c - 'a'];
          }
          node->isKey = true;
      }
      
      bool search(string word) {
          return helper(word, root);
      }
  
  private:
      TrieNode* root;
      
      bool helper(string word, TrieNode* node){
          for(int i = 0; i < word.size(); i++){
              char c = word[i];
              if(c != '.'){
                  if(!node->next[c - 'a']) return false;
                  node = node->next[c - 'a'];
              }
              else{
                  bool found = false;
                  int j = 0;
                  for(; j < 26; j++){
                      if(node->next[j]) found |= helper(word.substr(i + 1), node->next[j]);
                      if(found) return true;
                  }
                  if(j == 26) return false;
              }
          }
          return node->isKey;
      }
  };