Design Add and Search Words Data Structure 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)
Addsword
to the data structure, it can be matched later.bool search(word)
Returnstrue
if there is any string in the data structure that matchesword
orfalse
otherwise.word
may contain dots'.'
where dots can be matched with any letter.
Example:
Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output[null,null,null,null,false,true,true,true]
Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord(“bad”); wordDictionary.addWord(“dad”); wordDictionary.addWord(“mad”); wordDictionary.search(“pad”); // return False wordDictionary.search(“bad”); // return True wordDictionary.search(“.ad”); // return True wordDictionary.search(“b..”); // return True
Constraints:
1 <= word.length <= 25
word
inaddWord
consists of lowercase English letters.word
insearch
consist of'.'
or lowercase English letters.- There will be at most
3
dots inword
forsearch
queries. - At most
104
calls will be made toaddWord
andsearch
.
Design Add and Search Words Data Structure Solutions
✅Time:
✅Space:
C++
struct TrieNode {
vector<TrieNode*> children;
bool isWord = false;
TrieNode() : children(26) {}
~TrieNode() {
for (TrieNode* child : children)
delete child;
}
};
class WordDictionary {
public:
void addWord(const string& word) {
TrieNode* node = &root;
for (const char c : word) {
const int i = c - 'a';
if (!node->children[i])
node->children[i] = new TrieNode;
node = node->children[i];
}
node->isWord = true;
}
bool search(const string& word) {
return dfs(word, 0, &root);
}
private:
TrieNode root;
bool dfs(const string& word, int s, TrieNode* node) {
if (s == word.length())
return node->isWord;
if (word[s] != '.') {
TrieNode* next = node->children[word[s] - 'a'];
return next ? dfs(word, s + 1, next) : false;
}
// word[s] == '.' -> search all 26 children
for (int i = 0; i < 26; ++i)
if (node->children[i] && dfs(word, s + 1, node->children[i]))
return true;
return false;
}
};
Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public boolean isWord = false;
}
class WordDictionary {
public void addWord(String word) {
TrieNode node = root;
for (final char c : word.toCharArray()) {
final int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new TrieNode();
node = node.children[i];
}
node.isWord = true;
}
public boolean search(String word) {
return dfs(word, 0, root);
}
private TrieNode root = new TrieNode();
private boolean dfs(String word, int s, TrieNode node) {
if (s == word.length())
return node.isWord;
if (word.charAt(s) != '.') {
TrieNode next = node.children[word.charAt(s) - 'a'];
return next == null ? false : dfs(word, s + 1, next);
}
// word.charAt(s) == '.' -> search all 26 children
for (int i = 0; i < 26; ++i)
if (node.children[i] != null && dfs(word, s + 1, node.children[i]))
return true;
return false;
}
}
Python
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word: str) -> None:
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['isWord'] = True
def search(self, word: str) -> bool:
return self.dfs(word, 0, self.root)
def dfs(self, word: str, s: int, node: dict) -> bool:
if s == len(word):
return 'isWord' in node
if word[s] != '.':
if word[s] in node:
return self.dfs(word, s + 1, node[word[s]])
return False
for c in string.ascii_lowercase:
if c in node and self.dfs(word, s + 1, node[c]):
return True
return False
Watch Tutorial
Checkout more Solutions here