211. Add and Search Word - Data structure design.md

211. Add and Search Word - Data structure design

思路

这题其实就是208. Implement Trie(Prefix Tree)的升级版，会做208题此题就没啥问题了。 不同的地方就是查询时.可以代替任意字符，所以一旦有了.，就需要查找所有的子树，典型的DFS的问题。

C++

class TrieNode{
public:
   bool isLeaf;
   vector<TrieNode *>nexts = vector<TrieNode *>(26, NULL);
   TrieNode(bool _isLeaf){
       isLeaf = _isLeaf;
   } 
};

class WordDictionary {
private:
   TrieNode *root = new TrieNode(false);
public:
   /** Initialize your data structure here. */
   WordDictionary() {}
   
   /** Adds a word into the data structure. */
   void addWord(string word) {
       TrieNode *p = root;
       for(char c: word){
           if(p -> nexts[c-'a'] == NULL){
               TrieNode *node = new TrieNode(false);
               p -> nexts[c-'a'] = node;
               p = node;
           }
           else p = p -> nexts[c-'a'];
       }
       p -> isLeaf = true;
   }
   
   bool DFS(const string &word, TrieNode *node, int start){
       if(start == word.size()) return node -> isLeaf;
       
       if(word[start] == '.'){
           for(TrieNode *p: node -> nexts)
               if(p != NULL && DFS(word, p, start+1)) return true;
           return false;
       }
       
       TrieNode *p = node -> nexts[word[start] - 'a'];
       if(!p) return false;
       return DFS(word, p, start + 1);
   }
   
   /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
   bool search(string word) {
       return DFS(word, root, 0);
   }
};