Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();trie.insert("apple");trie.search("apple"); // returns truetrie.search("app"); // returns falsetrie.startsWith("app"); // returns truetrie.insert("app"); trie.search("app"); // returns true Note:
- You may assume that all inputs are consist of lowercase letters
a-z. - All inputs are guaranteed to be non-empty strings.
Trie的基本实现：
1 struct TrieNode{ 2 TrieNode* children[26]; 3 bool isWord; 4 TrieNode(){ 5 for(int i=0;i<26;i++){ 6 children[i]=NULL; 7 } 8 } 9 ~TrieNode(){10 for(int i=0;i<26;i++){11 delete children[i];12 }13 }14 };15 class Trie {16 private:17 TrieNode* root;18 public:19 /** Initialize your data structure here. */20 Trie() {21 root = new TrieNode();22 }23 24 /** Inserts a word into the trie. */25 void insert(string word) {26 TrieNode* curr = root;27 for(auto c: word){28 if(curr->children[c-'a']==NULL){29 curr->children[c-'a'] = new TrieNode();30 }31 curr = curr->children[c-'a'];32 }33 curr->isWord = true;34 }35 36 /** Returns if the word is in the trie. */37 bool search(string word) {38 TrieNode* curr = root;39 for(auto c: word){40 if(curr->children[c-'a']==NULL){41 return false; 42 }43 curr = curr->children[c-'a'];44 }45 46 return curr->isWord;47 }48 49 /** Returns if there is any word in the trie that starts with the given prefix. */50 bool startsWith(string prefix) {51 TrieNode* curr = root;52 for(auto c: prefix){53 if(curr->children[c-'a']==NULL){54 return false;55 }56 curr=curr->children[c-'a'];57 }58 59 return true;60 }61 };62 63 /**64 * Your Trie object will be instantiated and called as such:65 * Trie obj = new Trie();66 * obj.insert(word);67 * bool param_2 = obj.search(word);68 * bool param_3 = obj.startsWith(prefix);69 */