🎨Now live: Try our Free AI Image Generation Feature

Description
The WordDictionary
class implements a data structure that supports adding new words and searching for words, including the ability to use wildcard characters (.
) that can match any letter.
Intuition
The primary intuition behind this problem is to use a Trie (prefix tree) to efficiently store and search for words. A Trie allows for fast insertion and lookup operations, making it suitable for handling words and their prefixes.
Approach
- TrieNode Class:
- Represents each node in the Trie.
- Contains a dictionary
children
to store child nodes and a booleanisEndOfWord
to mark the end of a word. - WordDictionary Class:
- Initializes the Trie with a root
TrieNode
. -addWord
method adds a word to the Trie by iterating through each character of the word and creating nodes as necessary. -search
method performs a depth-first search (DFS) to handle the wildcard character.
: - If the current character is.
, it recursively checks all possible child nodes. - If the character matches, it moves to the next level in the Trie. - If the end of the word is reached, it checks if the current node marks the end of a word.
Complexity
Time Complexity:
addWord
: O(n), where n is the length of the word being added. This is because each character of the word is processed once.search
: O(m * n), where m is the number of nodes in the Trie and n is the length of the word being searched. The worst case occurs when every character in the word is a wildcard, leading to a full traversal of the Trie.
Space Complexity:
- The space complexity is primarily determined by the number of nodes in the Trie. In the worst case, the Trie could have a node for every character in every word added, leading to a space complexity of O(N * L), where N is the number of words and L is the average length of the words.
Code
C++
class WordDictionary {
public:
WordDictionary() {
// Constructor
}
void addWord(string word) {
wordsSet.insert(word);
}
bool search(string word) {
for (const string& savedWord : wordsSet) {
if (savedWord.length() != word.length()) continue;
bool wordsMatch = true;
for (int i = 0; i < word.length(); i++) {
if (word[i] != '.' && savedWord[i] != word[i]) {
wordsMatch = false;
break;
}
}
if (wordsMatch) return true;
}
return false;
}
private:
unordered_set wordsSet;
};
Python
class TrieNode:
def __init__(self):
self.children = {}
self.isEndOfWord = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.isEndOfWord = True
def search(self, word: str) -> bool:
def dfs(node, i):
if i == len(word):
return node.isEndOfWord
if word[i] == '.':
for child in node.children.values():
if dfs(child, i + 1):
return True
elif word[i] in node.children:
return dfs(node.children[word[i]], i + 1)
return False
return dfs(self.root, 0)
Java
class WordDictionary {
private List wordsList;
public WordDictionary() {
wordsList = new ArrayList<>();
}
public void addWord(String word) {
wordsList.add(word);
}
public boolean search(String word) {
for (String savedWord : wordsList) {
if (savedWord.length() != word.length()) continue;
boolean wordsMatch = true;
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) != '.' && savedWord.charAt(i) != word.charAt(i)) {
wordsMatch = false;
break;
}
}
if (wordsMatch) return true;
}
return false;
}
}
JavaScript
var WordDictionary = function() {
this.wordsSet = new Set();
};
/**
* @param {string} word
* @return {void}
*/
WordDictionary.prototype.addWord = function(word) {
this.wordsSet.add(word);
};
WordDictionary.prototype.search = function(word) {
for (const savedWord of this.wordsSet) {
if (savedWord.length !== word.length) continue;
let wordsMatch = true;
for (let i = 0; i < word.length; i++) {
if (word[i] !== '.' && savedWord[i] !== word[i]) {
wordsMatch = false;
break;
}
}
if (wordsMatch) return true;
}
return false;
};