leetcode208 前缀树

 1 class Trie {
 2 public:
 3     vector children;
 4     bool isEnd;
 5 
 6     /** Initialize your data structure here. */
 7     Trie():children(26),isEnd(false)
 8     {
 9     }
10     
11     /** Inserts a word into the trie. */
12     void insert(string word) 
13     {
14         Trie* node = this;
15         for(auto temp:word)
16         {
17             temp -= ‘a‘;
18             if(node->children[temp] == nullptr)
19             {
20                 node->children[temp] = new Trie();
21             }
22             node = node->children[temp];
23         }
24         node->isEnd = true;
25     }
26     
27     /** Returns if the word is in the trie. */
28     bool search(string word) 
29     {
30         Trie* node = this;
31         for(auto temp:word)
32         {
33             temp -= ‘a‘;
34             if(node->children[temp] != nullptr)
35             node = node->children[temp];
36             else
37             return false;
38         }
39         if(node->isEnd)
40         return true;
41         else
42         return false;        
43     }
44     
45     /** Returns if there is any word in the trie that starts with the given prefix. */
46     bool startsWith(string prefix) 
47     {
48         Trie* node = this;
49         for(auto temp:prefix)
50         {
51             temp -= ‘a‘;
52             if(node->children[temp] != nullptr)
53             node = node->children[temp];
54             else
55             return false;
56         }
57         return true;
58     }
59 };
60 
61 /**
62  * Your Trie object will be instantiated and called as such:
63  * Trie* obj = new Trie();
64  * obj->insert(word);
65  * bool param_2 = obj->search(word);
66  * bool param_3 = obj->startsWith(prefix);
67  */