Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Trie {
- private:
- bool end;
- Trie* children[26];
- public:
- /** Initialize your data structure here. */
- Trie() {
- end = false;
- memset(children, NULL, sizeof children);
- }
- /** Inserts a word into the trie. */
- void insert(string word) {
- Trie *node = this;
- for(char c: word){
- c -= 'a';
- if(!node->children[c])
- node->children[c] = new Trie();
- node = node->children[c];
- }
- node->end = true;
- }
- /** Returns if the word is in the trie. */
- bool search(string word) {
- Trie *node = this;
- for(char c: word){
- c -= 'a';
- if(!node->children[c])
- return false;
- node = node->children[c];
- }
- return node->end;
- }
- /** Returns if there is any word in the trie that starts with the given prefix. */
- bool startsWith(string prefix) {
- Trie *node = this;
- for(char c: prefix){
- c -= 'a';
- if(!node->children[c])
- return false;
- node = node->children[c];
- }
- return true;
- }
- };
- /**
- * Your Trie object will be instantiated and called as such:
- * Trie* obj = new Trie();
- * obj->insert(word);
- * bool param_2 = obj->search(word);
- * bool param_3 = obj->startsWith(prefix);
- */
Add Comment
Please, Sign In to add comment