Description
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.
设计一个包含下面两个操作的数据结构：addWord(word), search(word)
addWord(word)会在数据结构中添加一个单词。而search(word)则支持普通的单词查询或是只包含.和a-z的简易正则表达式的查询。
一个 . 可以代表一个任何的字母。
Examples
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Answer
Trie is a kind of data structure that often used as a dictionary, when add and search operations are commonly used. Trie has a standard form and it is easy to remember. This question is a basic question to learn about Trie.
Code
C++
class Node
{
public:
bool word;
Node* children[26];
Node(){
word = false;
memset(children, NULL, sizeof(children));
}
};
class WordDictionary {
public:
/** Initialize your data structure here. */
WordDictionary() {
}
/** Adds a word into the data structure. */
void addWord(string word) {
Node* node = root;
for(char c : word)
{
if(!node->children[c - 'a'])
node->children[c - 'a'] = new Node();
node = node->children[c - 'a'];
}
node->word = 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.s_str(), root);
}
private:
Node* root = new Node();
bool search(const char* word, Node* node)
{
for(int i = 0; word[i] && node; ++i)
{
if(word[i] != '.')
node = node->children[word[i] - 'a'];
else
{
Node* temp = node;
for(int j = 0; j < 26; ++j)
{
node = temp->children[j];
if(search(word + i + 1, node)) return true;
}
}
}
return node && node->word;
}
};
