Trie

字典树
 1 class Trie {
 2     public:
 3         Trie() {
 4             root = new Node();
 5         }
 6 
 7         ~Trie() {
 8             destroy(root);
 9         }
10 
11         void insert(string word) {
12             Node* next = root;
13             for (int i = 0; i < word.length(); ++i) {
14                 if (next->next[word[i] - 'a'] == NULL) {
15                     next->next[word[i] - 'a'] = new Node();
16                 }
17                 next = next->next[word[i] - 'a'];            
18             }
19             next->val++; // 只要最尾个字符的位置计数
20         }
21 
22         int search(string word) {
23             Node* next = root;
24             int i = 0;
25             for (; i < word.length() && next != NULL; ++i) {
26                 next = next->next[word[i] - 'a'];
27             }
28             if (i == word.length() && next != NULL) {
29                 return next->val;
30             } else {
31                 return 0;
32             }    
33         }
34 
35     private:
36         struct Node {
37             int val;
38             Node *next[26];
39             Node(): val(0) {
40                 memset(next, 0, sizeof(Node*) * 26);
41             }
42         };
43 
44         void destroy(Node* p) {
45             if (p == NULL) return;
46             for (int i = 0; i < 26; ++i) {
47                 destroy(p->next[i]);
48             }
49             delete p;
50         }
51         Node* root;    
52 };