[leetcode] 211 Add and Search Word

因为给定了a-z这个范围，并且字符串的添加和查找符合Trie的常用方法，因此考虑使用Trie这种数据结构。

然后和普通的Trie不同的是，要匹配正则表达式中的“.”，也就是说在这一层是无法判断沿着拿个结点向下走的，所以要循环这一层的结点，只有这一层所有结果失败后才能返回false，剩下的递推。所以我们采取Trie+回溯法。

代码中的searchHelp函数是专门用于回溯的，要求会回溯的掌握比较好。

class Trie{public:Trie *next[26];int flag;Trie():flag(0){for(int i=0;i<26;i++)next[i]=0;} };class WordDictionary {private:Trie *root;public:WordDictionary(){root=new Trie();}// Adds a word into the data structure.void addWord(string word) {Trie *p=root;for(int i=0;i<word.length();i++){if(p->next[word[i]-'a']==NULL){p->next[word[i]-'a']=new Trie();}p=p->next[word[i]-'a'];}p->flag=1;}// Returns if the word is in the data structure. A word could// contain the dot character '.' to represent any one letter.bool search(string word) {int n=word.length();return searchHelp(word,0,root,n);}bool searchHelp(string &word,int cur,Trie *root,int n){if(root==NULL)return false;if(cur==n){if(root->flag)return true;return false;}if(word[cur]=='.'){for(int i=0;i<26;i++){if(root->next[i])if(searchHelp(word,cur+1,root->next[i],n))return true;// return searchHelp(word,cur+1,root->next[i],n)// is wrong.because maybe another node is ok}}else{int temp=word[cur]-'a';if(root->next[temp])return searchHelp(word,cur+1,root->next[temp],n);return false;}//return false;}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

，可偏偏。多么温柔，一出口便是相互指责和嘲讽。