首页 > 其他 > 详细

leetcode208 前缀树

时间:2021-09-21 00:28:47      阅读:4      评论:0      收藏:0      [点我收藏+]

其实就是一个用于存储字符的多叉树,每一个节点代表一个字符。每个节点还维护一个bool变量用于判断是否为某一字符串的结尾。通过数组实现,贴代码

 1 class Trie {
 2 public:
 3     vector<Trie*> 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  */

 

leetcode208 前缀树

原文:https://www.cnblogs.com/zhaohhhh/p/15305301.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!