题目：
Implement a trie withinsert,search, andstartsWithmethods.
Note:You may assume that all inputs are consist of lowercase lettersa-z.
实现Trie的插入，查找，前缀查找操作。
假设所有输入都是由小写字母组成。
思路：
Trie树定义：https://zh.wikipedia.org/wiki/Trie。
Trie结点定义为：
class TrieNode {public:// Initialize your data structure here.bool isWord;TrieNode *next[26];TrieNode(){isWord = false;for(int i = 0 ; i < 26 ; i++)next[i] = NULL;}};其中isWord表示从根结点到当前结点的路径是否为一个单词。如果p->next[0]非空表示当前结点下有字符’a’。
代码：
class TrieNode {public:// Initialize your data structure here.bool isWord;TrieNode *next[26];TrieNode(){isWord = false;for(int i = 0 ; i < 26 ; i++)next[i] = NULL;}};class Trie {public:Trie(){root = new TrieNode();}// Inserts a word into the trie.void insert(string word){int len = word.size();TrieNode *p = root;for(int i = 0 ; i < len ; i++){//如果不存在，则建立新结点。如果存在，则继续向下if(p->next[word[i] – 'a'] == NULL)p->next[word[i] – 'a'] = new TrieNode();p = p->next[word[i] – 'a'];}p->isWord = true; //把最后一个结点的isWord置为true，表示从根结点到当前结点保存了一个单词}// Returns if the word is in the trie.bool search(string word){TrieNode *p = find(word);return p != NULL && p->isWord; //还要判断当前结点的isWord是否为真，为真才表示是个单词。如果为假，则表示word只是已存在单词的前缀}// Returns if there is any word in the trie// that starts with the given prefix.bool startsWith(string prefix){TrieNode *p = find(prefix);return p != NULL; //和上面一个函数比较，这里由于查找前缀，因此不需要判断isWord}//查找key是否存在TrieNode *find(string key){int len = key.size();TrieNode *p = root;for(int i = 0 ; i < len && p != NULL ; i++){p = p->next[key[i] – 'a'];}return p;}private:TrieNode* root;//注意：根结点并不表示字符};// Your Trie object will be instantiated and called as such:// Trie trie;// trie.insert("somestring");// trie.search("key");
版权声明：转载请注明出处。
，在这个阳光明媚的三月，我从我单薄的青春里打马而过，
