【LeetCode208】实现Trie(前缀树)

举报
野猪佩奇996 发表于 2022/01/22 23:52:01 2022/01/22
【摘要】 1.题目 2.思路 这里的前缀树,即“二十六叉树”,但是对于每个结点(对象),我们可以隐性存储一个字符——每个结点(对象)含有一个size为26的指针数组。接着就从根结点开始遍历判断。 注意: ...

1.题目

在这里插入图片描述
在这里插入图片描述

2.思路

这里的前缀树,即“二十六叉树”,但是对于每个结点(对象),我们可以隐性存储一个字符——每个结点(对象)含有一个size为26的指针数组。接着就从根结点开始遍历判断。
注意:
(1)this指针是指向当前对象的指针,又本题中调用这几个函数的使用对象均是根结点,所以下面的this指针指向根结点自己。

(2)C++中考虑防止内存泄漏,需要加上析构函数。

3.代码

class Trie {
private:
    bool isEnd;//记录该结点是否是一个串的结束
    Trie* next[26];//对象指针数组
public:
    /** Initialize your data structure here. */
    Trie() {//构造函数
        isEnd=false;
        memset(next,0,sizeof(next));//给数组赋初值0
        //或者写for(int i = 0; i < 26; i++) son[i] = NULL;
    }
    ~Trie(){//析构函数
        for(int i=0;i<26;i++){
            if(next[i]!=NULL){
                delete next[i];
            }
        }
    }
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* node=this;
        for(char c:word){
            int cur=c-'a';
            if(node->next[cur]==NULL){
                node->next[cur]=new Trie;
            }
            node=node->next[cur];
        }
        node->isEnd=true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* node=this;
        for(char c:word){
            int cur=c-'a';
            node=node->next[cur];
            if(node==NULL){
                return false;
            }
        }
        return node->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie* node=this;
        for(char c:prefix){
            int cur=c-'a';
            if(node->next[cur]==NULL){
                return false;
            }
            node=node->next[cur];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65

文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。

原文链接:andyguo.blog.csdn.net/article/details/116133905

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。