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); */
