Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase lettersa-z.
Analyse: For each node, it has 26 children, from a-z.
1. For the string insertion operation, the procedure is:
--Set root as the temp node;
--For every character in the string, compute its corresponding place at the branch, and mark them.
--After all characters are marked, set isVal to indicate it's a value rather than a prefix.
2. For the search operation, the procedure is:
--Set root as the temp node;
--For every character in the string, continuously check the existance of it. If NULL node encountered, jump out the of loop.
--If the node is empty, then return false; Else, we need to judge whether this string is a value or a prefix.
3. For the startWith operation, it's quite similiar to the search operation except that all search operations with true result returned can return true in the start operation.
Runtime: 64ms.
1 class TrieNode { 2 public: 3 // Initialize your data structure here. 4 TrieNode* childNode[26]; 5 bool isVal;//to indicate whether the leaf node is the target word or the prefix 6 TrieNode() { 7 isVal = false; 8 for(int i = 0; i < 26; i++) 9 childNode[i] = NULL;10 }11 };12 13 class Trie {14 public:15 Trie() {16 root = new TrieNode();17 }18 19 // Inserts a word into the trie.20 void insert(string word) {21 TrieNode* temp = root;22 for(int i = 0; i < word.size(); i++){23 if(temp->childNode[word[i] - 'a'] == NULL)24 temp->childNode[word[i] - 'a'] = new TrieNode();25 temp = temp->childNode[word[i] - 'a'];26 }27 temp->isVal = true; //if the word is inserted, then isVal is true28 }29 30 // Returns if the word is in the trie.31 bool search(string word) {32 TrieNode* temp = root;33 for(int i = 0; i < word.size(); i++){34 if(temp == NULL) break;35 temp = temp->childNode[word[i] - 'a'];36 }37 if(!temp) return false; //if the route does not exist, return false38 return temp->isVal; 39 }40 41 // Returns if there is any word in the trie42 // that starts with the given prefix.43 bool startsWith(string prefix) {44 TrieNode* temp = root;45 for(int i = 0; i < prefix.size(); i++){46 if(temp == NULL) break;47 temp = temp->childNode[prefix[i] - 'a'];48 }49 if(temp) 50 return true; //if the route exists, return true51 else 52 return false; //if the route doesn't exists, return false53 }54 55 private:56 TrieNode* root;57 };58 59 // Your Trie object will be instantiated and called as such:60 // Trie trie;61 // trie.insert("somestring");62 // trie.search("key");