304 North Cardinal St.
Dorchester Center, MA 02124

# Design Add and Search Words Data Structure LeetCode Solution

## Problem – Design Add and Search Words Data Structure LeetCode Solution

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the `WordDictionary` class:

• `WordDictionary()` Initializes the object.
• `void addWord(word)` Adds `word` to the data structure, it can be matched later.
• `bool search(word)` Returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter.

Example:

``````Input
Output
[null,null,null,null,false,true,true,true]
wordDictionary.search("b.."); // return True``````

Constraints:

• `1 <= word.length <= 25`
• `word` in `addWord` consists of lowercase English letters.
• `word` in `search` consist of `'.'` or lowercase English letters.
• There will be at most `3` dots in `word` for `search` queries.
• At most `104` calls will be made to `addWord` and `search`.

## Design Add and Search Words Data Structure LeetCode Solution in Java

``````public class WordDictionary {
public class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String item = "";
}

private TrieNode root = new TrieNode();

TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.item = word;
}

public boolean search(String word) {
return match(word.toCharArray(), 0, root);
}

private boolean match(char[] chs, int k, TrieNode node) {
if (k == chs.length) return !node.item.equals("");
if (chs[k] != '.') {
return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
} else {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null) {
if (match(chs, k + 1, node.children[i])) {
return true;
}
}
}
}
return false;
}
}
``````

## Design Add and Search Words Data Structure LeetCode Solution in Python

``````class TrieNode():
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False

class WordDictionary(object):
def __init__(self):
self.root = TrieNode()

node = self.root
for w in word:
node = node.children[w]
node.isWord = True

def search(self, word):
node = self.root
self.res = False
self.dfs(node, word)
return self.res

def dfs(self, node, word):
if not word:
if node.isWord:
self.res = True
return
if word[0] == ".":
for n in node.children.values():
self.dfs(n, word[1:])
else:
node = node.children.get(word[0])
if not node:
return
self.dfs(node, word[1:])
``````

## Design Add and Search Words Data Structure LeetCode Solution in C++

``````class TrieNode {
public:
bool word;
TrieNode* children[26];
TrieNode() {
word = false;
memset(children, NULL, sizeof(children));
}
};

class WordDictionary {
public:
/** Initialize your data structure here. */
WordDictionary() {

}

/** Adds a word into the data structure. */
TrieNode* node = root;
for (char c : word) {
if (!node -> children[c - 'a']) {
node -> children[c - 'a'] = new TrieNode();
}
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.c_str(), root);
}
private:
TrieNode* root = new TrieNode();

bool search(const char* word, TrieNode* node) {
for (int i = 0; word[i] && node; i++) {
if (word[i] != '.') {
node = node -> children[word[i] - 'a'];
} else {
TrieNode* tmp = node;
for (int j = 0; j < 26; j++) {
node = tmp -> children[j];
if (search(word + i + 1, node)) {
return true;
}
}
}
}
return node && node -> word;
}
};
``````
##### Design Add and Search Words Data Structure LeetCode Solution Review:

In our experience, we suggest you solve this Design Add and Search Words Data Structure LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Design Add and Search Words Data Structure LeetCode Solution

Find on Leetcode

##### Conclusion:

I hope this Design Add and Search Words Data Structure LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions