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