Add and Search Word - Data structure design
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.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
Trie树的递归版。
class TrieNode
{
public:
TrieNode* children[];
bool end;
TrieNode()
{
for(int i = ; i < ; i ++)
children[i] = NULL;
end = false;
}
}; class WordDictionary {
public:
WordDictionary()
{
root = new TrieNode();
} // Adds a word into the data structure.
void addWord(string word) {
TrieNode* cur = root;
int i = ;
while(i < word.size() && cur->children[word[i]-'a'] != NULL)
{
cur = cur->children[word[i]-'a'];
i ++;
}
if(i == word.size())
cur->end = true;
else
{
while(i < word.size())
{
cur->children[word[i]-'a'] = new TrieNode();
cur = cur->children[word[i]-'a'];
i ++;
}
cur->end = true;
}
} // 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) {
return search(word, root);
} bool search(string word, TrieNode* cur)
{
if(cur == NULL)
return false;
else if(word == "")
return (cur->end == true);
else
{
if(word[] != '.')
{
if(cur->children[word[]-'a'] == NULL)
return false;
else
return search(word.substr(), cur->children[word[]-'a']);
}
else
{
for(int i = ; i < ; i ++)
{
if(search(word.substr(), cur->children[i]))
return true;
}
return false;
}
}
} TrieNode* root;
}; // Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");