211. 添加与搜索单词 - 数据结构设计

211. 添加与搜索单词 - 数据结构设计

class WordDictionary {
public:struct Node{Node *node[26];bool is_end;Node(){is_end=false;for(int i=0;i< 26;i++){node[i]=NULL;}}};Node *root;WordDictionary() {root =new Node();}void addWord(string word) {auto p = root;for(auto  c : word){int i = c -'a';if(!p->node[i]) p->node[i] =new Node();p=p->node[i];}p->is_end =true;}bool search(string word) {return dfs(root,word,0);}bool dfs(Node * root ,string & s ,int i){if(i == s.size()) return root->is_end;if(s[i]!='.'){int n = s[i] - 'a';if(!root->node[n]) return false;return dfs(root ->node[n] , s, 1+i);}else{for(int j=0 ;j < 26;j++){if(root->node[j] &&dfs(root ->node[j] , s, 1+i)) return true;}return false;}}
};/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj = new WordDictionary();* obj->addWord(word);* bool param_2 = obj->search(word);*/