Dare2Solve
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.
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.
TrieNode Class:
children
to store child nodes and a boolean isEndOfWord
to mark the end of a word.WordDictionary Class:
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 .
:
.
, it recursively checks all possible child nodes.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.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<string> wordsSet;
};
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)
class WordDictionary {
private List<String> 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;
}
}
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;
};