Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

思路：应该就是字典树。

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