208. Implement Trie (Prefix Tree)

01//Runtime: 548 ms, faster than 5.04% of C++ online submissions for Implement Trie (Prefix Tree).
02//Memory Usage: 23.9 MB, less than 100.00% of C++ online submissions for Implement Trie (Prefix Tree).
03
04class Trie {
05public:
06    set<string> words;
07    /** Initialize your data structure here. */
08    Trie() {
09    }
10    
11    /** Inserts a word into the trie. */
12    void insert(string word) {
13        words.insert(word);
14    }
15    
16    /** Returns if the word is in the trie. */
17    bool search(string word) {
18        return words.find(word)!=words.end();
19    }
20    
21    /** Returns if there is any word in the trie that starts with the given prefix. */
22    bool startsWith(string prefix) {
23        for(set<string>::iterator it = words.begin(); it!=words.end(); it++){
24            if((*it).rfind(prefix, 0) == 0) return true;
25        }
26        return false;
27    }
28};
29
30/**
31 * Your Trie object will be instantiated and called as such:
32 * Trie* obj = new Trie();
33 * obj->insert(word);
34 * bool param_2 = obj->search(word);
35 * bool param_3 = obj->startsWith(prefix);
36 */
37 
38//Runtime: 92 ms, faster than 59.89% of C++ online submissions for Implement Trie (Prefix Tree).
39//Memory Usage: 48 MB, less than 30.86% of C++ online submissions for Implement Trie (Prefix Tree).
40class TrieNode{
41private:
42    vector<TrieNode*> links;
43    int R = 26;
44    bool isEnd = false;
45    
46public:    
47    TrieNode() {
48        links = vector<TrieNode*>(R);
49    }
50    
51    bool containsKey(char c){
52        return links[c-'a'] != NULL;
53    }
54    
55    TrieNode* get(char c){
56        return links[c-'a'];
57    }
58    
59    void put(char c, TrieNode* node){
60        links[c-'a'] = node;
61    }
62    
63    void setEnd(){
64        isEnd = true;
65    }
66    
67    bool getEnd(){
68        return isEnd;
69    }
70};
71
72class Trie {
73private:
74    TrieNode *root;
75    
76    // search a prefix or whole key in trie and
77    // returns the node where search ends
78    TrieNode* searchPrefix(string word){
79        TrieNode *node = root;
80        for(char c : word){
81            if(node->containsKey(c)){
82                node = node->get(c);
83            }else{
84                return NULL;
85            }
86        }
87        return node;
88    }
89    
90public:
91    /** Initialize your data structure here. */
92    Trie() {
93        root = new TrieNode();
94    }
95    
96    /** Inserts a word into the trie. */
97    //time: O(m), space: O(m), m is the key length.
98    void insert(string word) {
99        TrieNode *node = root;
100        for(char c : word){
101            if(!node->containsKey(c)){
102                node->put(c, new TrieNode());
103            }
104            node = node->get(c);
105        }
106        node->setEnd();
107    }
108    
109    /** Returns if the word is in the trie. */
110    //time: O(m), space: O(1)
111    bool search(string word) {
112        TrieNode *node = searchPrefix(word);
113        return node != NULL && node->getEnd();
114    }
115    
116    /** Returns if there is any word in the trie that starts with the given prefix. */
117    //time: O(m), space: O(1)
118    bool startsWith(string prefix) {
119        TrieNode *node = searchPrefix(prefix);
120        return node != NULL;
121    }
122};
123
124//Runtime: 124 ms, faster than 45.63% of C++ online submissions for Implement Trie (Prefix Tree).
125//Memory Usage: 48.1 MB, less than 16.67% of C++ online submissions for Implement Trie (Prefix Tree).
126class TrieNode{
127public:
128    bool isEnd;
129    vector<TrieNode*> children;
130    char c;
131    
132    TrieNode(char c = '\0'){
133        isEnd = false;
134        this->c = c;
135        children = vector<TrieNode*>(26, nullptr);
136    }
137};
138
139class Trie {
140public:
141    TrieNode* root;
142    
143    /** Initialize your data structure here. */
144    Trie() {
145        root = new TrieNode();
146    }
147    
148    /** Inserts a word into the trie. */
149    void insert(string word) {
150        TrieNode* node = root;
151        for(char c : word){
152            if(node->children[c-'a'] == nullptr){
153                node->children[c-'a'] = new TrieNode(c);
154            }
155            node = node->children[c-'a'];
156        }
157        node->isEnd = true;
158    }
159    
160    /** Returns if the word is in the trie. */
161    bool search(string word) {
162        TrieNode* node = root;
163        for(char c : word){
164            if(node->children[c-'a'] == nullptr) return false;
165            node = node->children[c-'a'];
166        }
167        return node->isEnd;
168    }
169    
170    /** Returns if there is any word in the trie that starts with the given prefix. */
171    bool startsWith(string prefix) {
172        TrieNode* node = root;
173        for(char c : prefix){
174            if(node->children[c-'a'] == nullptr) return false;
175            node = node->children[c-'a'];
176        }
177        return true;
178    }
179};
180
181/**
182 * Your Trie object will be instantiated and called as such:
183 * Trie* obj = new Trie();
184 * obj->insert(word);
185 * bool param_2 = obj->search(word);
186 * bool param_3 = obj->startsWith(prefix);
187 */