Add and Search Word - Data structure design - LeetCode

 1 class DictNode
 2 {
 3 public:
 4     DictNode *dict[27];
 5     DictNode ()
 6     {
 7         for (int i = 0; i < 27; i++)
 8             dict[i] = NULL;
 9     }
10 };
11 class WordDictionary {
12 public:
13     WordDictionary()
14     {
15         root = new DictNode();
16     }
17     // Adds a word into the data structure.
18     void addWord(string word) {
19         DictNode *cur = root;
20         for (int i = 0, len = word.size(); i < len; i++)
21         {
22             int loc = (int)(word[i] - ‘a‘);
23             if (cur->dict[loc] == NULL)
24                 cur->dict[loc] = new DictNode();
25             cur = cur->dict[loc];
26         }
27         if (cur->dict[26] == NULL)
28             cur->dict[26] = new DictNode();
29     }
30     bool help(DictNode *cur, string word)
31     {
32         if (cur == NULL) return false;
33         if (word.size() == 0)
34         {
35             if (cur->dict[26] == NULL) return false;
36             return true;
37         }
38         if (word[0] != ‘.‘)
39         {
40             int loc = (int)(word[0] - ‘a‘);
41             return help(cur->dict[loc], (word.size() > 1 ? word.substr(1) : ""));
42         }
43         else
44         {
45             for (int i = 0; i < 26; i++) if (cur->dict[i] != NULL)
46             {
47                 if (help(cur->dict[i], (word.size() > 1 ? word.substr(1) : "")))
48                     return true;
49             }
50             return false;
51         }
52     }
53 
54     // Returns if the word is in the data structure. A word could
55     // contain the dot character ‘.‘ to represent any one letter.
56     bool search(string word) {
57         return help(root, word);
58     }
59 private:
60     DictNode *root;
61 };
62 
63 // Your WordDictionary object will be instantiated and called as such:
64 // WordDictionary wordDictionary;
65 // wordDictionary.addWord("word");
66 // wordDictionary.search("pattern");