Implement a trie with insert, search, and startsWith methods.
Note: You may assume that all inputs are consist of lowercase letters a-z.
Hide Tags Data Structure Trie
实现一棵Trie树以及实现查询的功能，根据上一篇文章中的分析和伪代码可以很迅速地实现： runtime:68ms
class TrieNode {public:// Initialize your data structure here.TrieNode() {words=0;prefixs=0;for(int i=0;i<26;i++)edges[i]=NULL;}int words;int prefixs;TrieNode* edges[26];};class Trie {public:Trie() {root = new TrieNode();}// Inserts a word into the trie.void insert(string word) {insertHelper(root,word,0);}// Returns if the word is in the trie.bool search(string word) {return searchHelper(root,word,0)!=0;}startsWith(string prefix) {return startsWithHelper(root,prefix,0)!=0;}void insertHelper(TrieNode * node,string &word,int pos) {if(pos==word.size()){node->words++;node->prefixs++;}else{node->prefixs++;int char_code=word[pos]-‘a’;if(node->edges[char_code]==NULL)node->edges[char_code]=new TrieNode();insertHelper(node->edges[char_code],word,pos+1);}}int searchHelper(TrieNode * node,string &word,int pos){int char_code=word[pos]-‘a’;if(pos==word.size())return node->words;else if(node->edges[char_code]==NULL)return 0;elsereturn searchHelper(node->edges[char_code],word,pos+1);}int startsWithHelper(TrieNode * node,string &word,int pos){int char_code=word[pos]-‘a’;if(pos==word.size())return node->prefixs;else if(node->edges[char_code]==NULL)return 0;elsereturn startsWithHelper(node->edges[char_code],word,pos+1);}private:TrieNode* root;};
，造物之前，必先造人。
