1 class TrieNode { 2 public: 3 const static int NR_FANOUT = 26; 4 TrieNode* child[NR_FANOUT]; 5 int count; 6 // Initialize your data structure here. 7 TrieNode() { 8 for (int i=0; i<NR_FANOUT; i++) { 9 child[i] = NULL; 10 } 11 count = 0; 12 } 13 }; 14 15 class Trie { 16 public: 17 Trie() { 18 root = new TrieNode(); 19 } 20 21 // Inserts a word into the trie. 22 void insert(string s) { 23 insert(s, 0, root); 24 } 25 26 // Returns if the word is in the trie. 27 bool search(string key) { 28 return search(key, 0, root) != NULL; 29 } 30 31 // Returns if there is any word in the trie 32 // that starts with the given prefix. 33 bool startsWith(string prefix) { 34 return search_prefix(prefix, 0, root) != NULL; 35 } 36 private: 37 TrieNode* insert(string& s, int pos, TrieNode* current) { 38 int len = s.size(); 39 if (pos > len) { 40 return NULL; 41 } 42 if (current == NULL) { 43 current = new TrieNode(); 44 } 45 if (pos == len) { 46 current->count++; 47 return current; 48 } 49 int idx = s[pos] - 'a'; 50 current->child[idx] = insert(s, pos + 1, current->child[idx]); 51 return current; 52 } 53 54 TrieNode* search(string& s, int pos, TrieNode* current) { 55 if (current == NULL) { 56 return NULL; 57 } 58 int len = s.size(); 59 if (pos > len) { 60 return NULL; 61 } else if (pos == len && current->count) { 62 return current; 63 } 64 return search(s, pos + 1, current->child[s[pos] - 'a']); 65 } 66 TrieNode* search_prefix(string& s, int pos, TrieNode* current) { 67 if (current == NULL) { 68 return NULL; 69 } 70 int len = s.size(); 71 if (pos >= len) { 72 return current; 73 } 74 return search_prefix(s, pos + 1, current->child[s[pos] - 'a']); 75 } 76 private: 77 TrieNode* root; 78 };
mplement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.