题意：实现添加单词和查找单词的作用，即实现字典功能。
思路：'.' 可以代表一个任何小写字母，可能是".abc"或者"a.bc"或者"abc."，能应对这三种就没有问题了。在每个单词的尾字母上标上tag=1，代表从树根到此节点有一个单词。暂时想不到更快的办法。
class WordDictionary {
public:
WordDictionary(){
tree=create();
}
void addWord(string word) {
node *tmp=tree;
node *p=; //负责创建结点
for(int i=; i<word.size(); i++)
{
if(!tmp->next[word[i]-'a']) //没有这个分支，创建它
{
p=create();
tmp->next[word[i]-'a']=p;
}
tmp=tmp->next[word[i]-'a']; //往下走
}
tmp->tag=;
}
bool search(string word) {
if(DFS(tree,word.c_str())==true)//搜
return true;
return false;
}
private:
struct node
{
bool tag;
node *next[];
};
node *tree;//先建立树根
node *create()
{
node *tmp=new(node);
tmp->tag=;
for(int i=; i<; i++)
tmp->next[i]=;
return tmp;
}
bool DFS(node *t,const char *p)
{
if(*(p+)=='\0')
{
if(*p=='.') //'.'刚好是最后一个
{
for(int i=; i<; i++)
if(t->next[i]&&t->next[i]->tag==)
return true;
return false; //无匹配
}
if(t->next[*p-'a'] && t->next[*p-'a']->tag==) return ;
return false;
}
if(*p=='.')//要搜索全部
{
for(int i=; i<; i++)
if( t->next[i] && DFS(t->next[i],p+) )
return true;
return false;
}
if( t->next[*p-'a'] && DFS(t->next[*p-'a'],p+))
return true;
return false;
}
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");AC代码