Design a data structure that supports adding new words and searching for words with a given pattern. The data structure should have two operations:
void addWord(word): Adds a word to the data structure.bool search(word): Returns true if the word is in the data structure and can be represented as a pattern by ‘.’ (dot), which matches any single character.
The ‘.’ (dot) in the pattern can represent any character.
Table of Contents
Sample Input/Output:
Let’s consider a series of operations on the data structure:
- Add “bad” to the data structure.
- Add “dad” to the data structure.
- Add “mad” to the data structure.
- Search for “pad” – Output: false.
- Search for “bad” – Output: true.
- Search for “.ad” – Output: true.
- Search for “b..” – Output: true.
Time and Space Complexity:
The time complexity for each operation (addWord and search) depends on the length of the word and the number of words in the data structure. The worst-case time complexity for both operations can be O(W), where W is the length of the longest word.
The space complexity of the data structure is O(N*M), where N is the total number of characters in all added words and M is the number of words.
C++ Solution:
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool isEnd;
TrieNode() {
isEnd = false;
}
};
class WordDictionary {
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode* node = root;
for (char ch : word) {
if (node->children.find(ch) == node->children.end()) {
node->children[ch] = new TrieNode();
}
node = node->children[ch];
}
node->isEnd = true;
}
bool search(string word) {
return searchWord(word, 0, root);
}
private:
TrieNode* root;
bool searchWord(string& word, int index, TrieNode* node) {
if (index == word.length()) {
return node->isEnd;
}
char ch = word[index];
if (ch == '.') {
for (const auto& [childChar, childNode] : node->children) {
if (searchWord(word, index + 1, childNode)) {
return true;
}
}
return false;
} else {
if (node->children.find(ch) == node->children.end()) {
return false;
}
return searchWord(word, index + 1, node->children[ch]);
}
}
};
int main() {
WordDictionary wordDict;
wordDict.addWord("bad");
wordDict.addWord("dad");
wordDict.addWord("mad");
cout << "Search 'pad': " << (wordDict.search("pad") ? "true" : "false") << endl; // Output: false
cout << "Search 'bad': " << (wordDict.search("bad") ? "true" : "false") << endl; // Output: true
cout << "Search '.ad': " << (wordDict.search(".ad") ? "true" : "false") << endl; // Output: true
cout << "Search 'b..': " << (wordDict.search("b..") ? "true" : "false") << endl; // Output: true
return 0;
}
In this implementation, we define a TrieNode class, similar to the previous Trie implementation, and a WordDictionary class that uses a Trie to store the words.
The addWord function adds a word to the Trie by creating new nodes as needed for each character in the word.
The search function performs a recursive search in the Trie for the given word with the help of the searchWord private function. If the character is a dot (‘.’), it explores all possible paths. Otherwise, it follows the exact character path in the Trie.
The main function demonstrates the usage of the WordDictionary by adding words and performing search operations with ‘.’ (dot) as a wildcard character.
The output for the provided test case will be:
Search 'pad': false
Search 'bad': true
Search '.ad': true
Search 'b..': true