211. 添加与搜索单词 - 数据结构设计

 1 class WordDictionary 
 2 {
 3     bool is_end;   //是否以该单词结尾
 4     WordDictionary* son[26]; //该节点儿子的个数
 5 
 6 public:
 7     WordDictionary() 
 8     {
 9         is_end = false;
10         for(int i = 0;i < 26;i ++) son[i] = NULL;
11     }
12     
13     void addWord(string word) 
14     {
15         auto p = this;
16         for(auto c : word) 
17         {
18             int u = c - ‘a‘;
19             if(p->son[u] == NULL) p->son[u] = new WordDictionary();
20             p = p->son[u];
21         }
22         p->is_end = true;
23     }
24     
25     bool search(string word) 
26     {
27         auto p = this;
28         if(p == NULL) return false;
29 
30         for(int i = 0; i < word.size(); ++ i)
31         {   
32             if (word[i] == ‘.‘)
33             {
34                 //如果为".",在26个儿子里面找,
35                 for(int j = 0; j < 26; ++ j)//有儿子且找到了，返回true
36                     if (p->son[j] && p->son[j]->search(word.substr(i + 1))) return true;
37                 return false;
38             }
39             else 
40             {
41                 int u = word[i] - ‘a‘;
42                 if(p->son[u] == NULL) return false;
43                 p = p->son[u];
44             }
45         }
46         return p->is_end;
47     }
48 };