# 211. 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`.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

LeetCode出新题的速度越来越快了，有点跟不上节奏的感觉了。这道题如果做过之前的那道 Implement Trie (Prefix Tree) 实现字典树(前缀树)的话就没有太大的难度了，还是要用到字典树的结构，唯一不同的地方就是search的函数需要重新写一下，因为这道题里面’.’可以代替任意字符，所以一旦有了’.’，就需要查找所有的子树，只要有一个返回true，整个search函数就返回true，典型的DFS的问题，其他部分跟上一道实现字典树没有太大区别，代码如下：

``````class WordDictionary {
public:
struct TrieNode {
public:
TrieNode *child[26];
bool isWord;
TrieNode() : isWord(false) {
for (auto &a : child) a = NULL;
}
};

WordDictionary() {
root = new TrieNode();
}

// Adds a word into the data structure.
void addWord(string word) {
TrieNode *p = root;
for (auto &a : word) {
int i = a - 'a';
if (!p->child[i]) p->child[i] = new TrieNode();
p = p->child[i];
}
p->isWord = 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 searchWord(word, root, 0);
}

bool searchWord(string &word, TrieNode *p, int i) {
if (i == word.size()) return p->isWord;
if (word[i] == '.') {
for (auto &a : p->child) {
if (a && searchWord(word, a, i + 1)) return true;
}
return false;
} else {
return p->child[word[i] - 'a'] && searchWord(word, p->child[word[i] - 'a'], i + 1);
}
}

private:
TrieNode *root;
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
``````

Implement Trie (Prefix Tree)

Wildcard Matching

https://leetcode.com/discuss/36246/my-java-trie-based-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation