# LeetCode Add and Search Word - Data structure design

LeetCode 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")
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.

```const int N = 26;
class WordDictionary {
private:
struct Node {
bool isWord;
vector<Node*> children;
Node(bool i) :isWord(i) {
for (int i = 0; i < N; ++i)children.push_back(NULL);
};
};
Node *root;
bool search(const string& word, int i, Node *root) {
if (root == NULL)return false;
int idx = word[i] - 'a';
if (i == word.size() - 1) {
if (word[i] != '.')return root->children[idx] != NULL&&root->children[idx]->isWord;
else {
for (int j = 0; j < N; ++j) {
if (root->children[j] != NULL&&root->children[j]->isWord)return true;
}
return false;
}
}
if (word[i] != '.')return search(word, i + 1, root->children[idx]);
else {
for (int j = 0; j < N; ++j) {
if (search(word, i + 1, root->children[j]))return true;
}
return false;
}
}
public:
/** Initialize your data structure here. */
WordDictionary() {
root = new Node(false);
}
/** Adds a word into the data structure. */
Node *cur = root;
for (const auto& c : word) {
int idx = c - 'a';
if (cur->children[idx] == NULL)cur->children[idx] = new Node(false);
cur = cur->children[idx];
}
cur->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) {
Node *cur = root;
return search(word, 0, cur);
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.