LeetCode 实现 Trie (前缀树)

比眉伴天荒 2023-06-04 13:58 141阅读 0赞

题目链接：[https://leetcode-cn.com/problems/implement-trie-prefix-tree/][https_leetcode-cn.com_problems_implement-trie-prefix-tree]

### 题目大意： ###

略。

### 分析： ###

字典树模板.

### 代码如下： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 class Trie {
     2 public:
     3     int passed; // 记录经过这个节点的字符串数量
     4     int ends;   // 记录有多少个字符串以这个节点结尾
     5     unordered_map< char, Trie* > nxt;
     6     
     7     /** Initialize your data structure here. */
     8     Trie() {
     9         passed = 0;
    10         ends = 0;
    11     }
    12     
    13     /** Inserts a word into the trie. */
    14     void insert(string word) {
    15         Trie* p = this;
    16         for(int i = 0; i < word.size(); ++i) {
    17             if(p->nxt.find(word[i]) == p->nxt.end()) {
    18                 p->nxt[word[i]] = new Trie();
    19             }
    20             ++p->passed;
    21             p = p->nxt[word[i]];
    22         }
    23         ++p->ends;
    24     }
    25     
    26     /** Returns if the word is in the trie. */
    27     bool search(string word) {
    28         Trie* p = this;
    29         for(int i = 0; i < word.size(); ++i) {
    30             if(p->nxt.find(word[i]) == p->nxt.end()) return false;
    31             p = p->nxt[word[i]];
    32         }
    33         return p->ends != 0;
    34     }
    35     
    36     /** Returns if there is any word in the trie that starts with the given prefix. */
    37     bool startsWith(string prefix) {
    38         Trie* p = this;
    39         for(int i = 0; i < prefix.size(); ++i) {
    40             if(p->nxt.find(prefix[i]) == p->nxt.end()) return false;
    41             p = p->nxt[prefix[i]];
    42         }
    43         return true;
    44     }
    45 };
    46 
    47 /**
    48  * Your Trie object will be instantiated and called as such:
    49  * Trie* obj = new Trie();
    50  * obj->insert(word);
    51  * bool param_2 = obj->search(word);
    52  * bool param_3 = obj->startsWith(prefix);
    53  */

转载于:https://www.cnblogs.com/zaq19970105/p/11457612.html

[https_leetcode-cn.com_problems_implement-trie-prefix-tree]: https://leetcode-cn.com/problems/implement-trie-prefix-tree/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/7d6fd95b20064c49b6fd119edd616d75.png