208. Implement Trie (Prefix Tree)

There is a very good video explaining what tries is though the implementation is Java.
https://www.youtube.com/watch?v=EjD5PJJoeLU

I followed the way video does to implement trie. I made a mistake in first place to initialize the TrieNode* array. I used 26 instead of sizeof(next). The third argument for memset actually should be computed as 26*sizeof(TrieNode*). Otherwise, you'll get run time error because of accessing invalid memory.

1:  class TrieNode {  
2:  public:  
3:    TrieNode *next[26];  
4:    bool isEnd;  
5:    // Initialize your data structure here.  
6:    TrieNode(bool b = false) {  
7:      memset(next, 0, sizeof(next));  
8:      isEnd = b;  
9:    }  
10:  };  
11:  class Trie {  
12:  public:  
13:    Trie() {  
14:      root = new TrieNode();  
15:    }  
16:    // Inserts a word into the trie.  
17:    void insert(string word) {  
18:      _insert(root, word, 0);  
19:    }  
20:    // Returns if the word is in the trie.  
21:    bool search(string word) {  
22:      return _search(root, word, 0);  
23:    }  
24:    // Returns if there is any word in the trie  
25:    // that starts with the given prefix.  
26:    bool startsWith(string prefix) {  
27:      return _startsWith(root, prefix, 0);  
28:    }  
29:  private:  
30:    TrieNode* root;  
31:    void _insert(TrieNode *node, string &word, int i) {  
32:      if (i == word.size()) {  
33:        node->isEnd = true;  
34:        return;  
35:      }  
36:      int j = word[i]-'a';  
37:      if (node->next[j] == NULL) node->next[j] = new TrieNode();  
38:      _insert(node->next[j], word, i+1);  
39:    }  
40:    bool _search(TrieNode *node, string &word, int i) {  
41:      if (i == word.size()) return node->isEnd;  
42:      int j = word[i]-'a';  
43:      if (node->next[j] == NULL) return false;  
44:      return _search(node->next[j], word, i+1);  
45:    }  
46:    bool _startsWith(TrieNode *node, string &prefix, int i) {  
47:      if (i == prefix.size()) return true;  
48:      int j = prefix[i]-'a';  
49:      if (node->next[j] == NULL) return false;  
50:      return _startsWith(node->next[j], prefix, i+1);  
51:    }  
52:  };  

Also, there is iterative way to implement it.

1:  #define R 26  
2:  class TrieNode {  
3:  public:  
4:    TrieNode *next[R];  
5:    bool isEnd;  
6:    // Initialize your data structure here.  
7:    TrieNode() {  
8:      memset(next, 0, R*sizeof(TrieNode*));  
9:      isEnd = false;  
10:    }  
11:  };  
12:  class Trie {  
13:  public:  
14:    Trie() {  
15:      root = new TrieNode();  
16:    }  
17:    // Inserts a word into the trie.  
18:    void insert(string word) {  
19:      TrieNode *p = root;  
20:      for (int i = 0; i < word.size(); i++) {  
21:        if (p->next[word[i]-'a'] == NULL) {  
22:          p->next[word[i]-'a'] = new TrieNode();  
23:        }  
24:        p = p->next[word[i]-'a'];  
25:      }  
26:      p->isEnd = true;  
27:    }  
28:    // Returns if the word is in the trie.  
29:    bool search(string word) {  
30:      TrieNode *p = find(word);  
31:      return p && p->isEnd;  
32:    }  
33:    // Returns if there is any word in the trie  
34:    // that starts with the given prefix.  
35:    bool startsWith(string prefix) {  
36:      return find(prefix) != NULL;  
37:    }  
38:  private:  
39:    TrieNode* root;  
40:    TrieNode *find(string word) {  
41:      TrieNode *p = root;  
42:      for (int i = 0; i < word.size() && p; i++) {  
43:        p = p->next[word[i]-'a'];  
44:      }  
45:      return p;  
46:    }  
47:  };  
48:  // Your Trie object will be instantiated and called as such:  
49:  // Trie trie;  
50:  // trie.insert("somestring");  
51:  // trie.search("key");*/