C++刷leetcode（208. 实现 Trie (前缀树)）【字典树】

糖逗

题目描述：

1. 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
   
2. 
   
3. 示例:
   
4. 
   
5. Trie trie = new Trie();
   
6. 
   
7. trie.insert("apple");
   
8. trie.search("apple");   // 返回 true
   
9. trie.search("app");     // 返回 false
   
10. trie.startsWith("app"); // 返回 true
    
11. trie.insert("app");   
    
12. trie.search("app");     // 返回 true
    
13. 说明:
    
14. 
    
15. 你可以假设所有的输入都是由小写字母 a-z 构成的。
    
16. 保证所有输入均为非空字符串。
    
17. 
    
18. 来源：力扣（LeetCode）
    
19. 链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
    
20. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

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

复制代码