Trie 树的一个应用
Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
class TrieNode{
public:
TrieNode* child[];
bool isWord = false;
TrieNode() : isWord(false){
for(auto &a : child)
a = nullptr;
}
};
class WordDictionary{
private:
TrieNode* root = new TrieNode();
public:
void addWord(string word){
TrieNode* p = root;
for(auto &a : word){
int i = a - 'a';
if(p->child[i] == nullptr) p->child[i] = new TrieNode();
p = p->child[i];
}
p->isWord = true;
}
bool search(string word){
int n = word.length();
return search(word,n,,root);
}
bool search(string& word,int n,int pos,TrieNode* cur){
if(pos == n) return cur->isWord;
if(cur == nullptr) return false;
if(word[pos] == '.'){
for(int i=;i<;i++){
if(cur->child[i]){
if(search(word,n,pos+,cur->child[i])){
return true;
}
}
}
}else{
int i = word[pos] - 'a';
if(cur->child[i])
return search(word,n,pos+,cur->child[i]);
}
return false;
}
};