Description
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)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay contain dots'.'where dots can be matched with any letter.
Examples:
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]Solution in Python
To solve this problem, we can use a Trie (prefix tree) data structure, which is well-suited for storing and searching words efficiently. The Trie structure will allow us to easily add words and perform searches, even when the search query contains wildcards (represented by a dot ‘.’).
Implementation Overview
- TrieNode Class:
- Each node in the Trie will store a dictionary where keys are characters and values are child nodes.
- Additionally, each node will have a boolean flag to indicate if the node represents the end of a valid word.
- WordDictionary Class:
- The
WordDictionaryclass will have a root node (an instance ofTrieNode). addWord(word)will traverse the Trie to add the word.search(word)will recursively check for the word in the Trie, handling wildcards (‘.’) appropriately.
- The
Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class WordDictionary:
def __init__(self):
# Initialize the root of the Trie
self.root = TrieNode()
def addWord(self, word: str) -> None:
# Start from the root node
current_node = self.root
# Traverse the Trie to add each character of the word
for char in word:
if char not in current_node.children:
# If the character is not in the current node's children, add a new node
current_node.children[char] = TrieNode()
# Move to the next node
current_node = current_node.children[char]
# After adding all characters, mark the last node as the end of a word
current_node.is_end_of_word = True
def search(self, word: str) -> bool:
# Helper function to search the Trie recursively
def search_in_node(node, word):
for i, char in enumerate(word):
if char == '.':
# If the current character is '.', we need to check all possible nodes at this level
for child in node.children.values():
if search_in_node(child, word[i + 1:]):
return True
return False
else:
# If the current character is not '.', check if it's in the Trie
if char not in node.children:
return False
# Move to the corresponding child node
node = node.children[char]
# After processing all characters, return whether we are at the end of a valid word
return node.is_end_of_word
# Start searching from the root node
return search_in_node(self.root, word)Explanation:
- TrieNode Class:
children: A dictionary to store the child nodes corresponding to each character.is_end_of_word: A boolean flag that indicates whether this node marks the end of a valid word.
- WordDictionary Class:
__init__: Initializes the root of the Trie.addWord: Adds a word to the Trie by iterating through each character and creating new nodes if necessary. Marks the end of the word.search: Searches for a word in the Trie. If a dot (‘.’) is encountered, it recursively searches all possible paths. It uses a helper functionsearch_in_nodeto handle the recursion.
Usage:
- Words can be added using
addWord. - Words can be searched using
search, and it returnsTrueif the word (or pattern with wildcards) is found, otherwiseFalse.
This implementation is efficient and handles all the constraints provided, making it suitable for up to 10^4 operations as stated in the problem.
Solution in Javascript
JavaScript
// Definition of TrieNode
class TrieNode {
constructor() {
this.children = {}; // Object to store child nodes
this.isEndOfWord = false; // Flag to indicate if this node is the end of a word
}
}
// Definition of WordDictionary
var WordDictionary = function() {
// Initialize the root of the Trie
this.root = new TrieNode();
};
/**
* @param {string} word
* @return {void}
*/
WordDictionary.prototype.addWord = function(word) {
let currentNode = this.root;
// Iterate through each character in the word
for (let char of word) {
// If the character is not already a child of the current node, add it
if (!currentNode.children[char]) {
currentNode.children[char] = new TrieNode();
}
// Move to the next node
currentNode = currentNode.children[char];
}
// Mark the last node as the end of the word
currentNode.isEndOfWord = true;
};
/**
* @param {string} word
* @return {boolean}
*/
WordDictionary.prototype.search = function(word) {
// Helper function for recursive search
const searchInNode = (node, word) => {
for (let i = 0; i < word.length; i++) {
const char = word[i];
if (char === '.') {
// If the current character is '.', check all possible children
for (let child of Object.values(node.children)) {
// Recursively search the remaining part of the word
if (searchInNode(child, word.slice(i + 1))) {
return true;
}
}
// If no child node matches, return false
return false;
} else {
// If the current character is not '.', move to the next node
if (!node.children[char]) {
return false; // Character not found
}
node = node.children[char];
}
}
// After processing all characters, check if we are at the end of a valid word
return node.isEndOfWord;
};
// Start the search from the root node
return searchInNode(this.root, word);
};Solution in Java
Java
// Definition of TrieNode class
class TrieNode {
public TrieNode[] children; // Array to store child nodes for each character 'a' to 'z'
public boolean isEndOfWord; // Flag to indicate if this node marks the end of a word
public TrieNode() {
this.children = new TrieNode[26]; // Initialize the array with 26 null entries (for 'a' to 'z')
this.isEndOfWord = false; // By default, a node is not the end of a word
}
}
// Definition of WordDictionary class
public class WordDictionary {
private TrieNode root; // Root node of the Trie
// Constructor to initialize the root node
public WordDictionary() {
root = new TrieNode();
}
// Method to add a word to the Trie
public void addWord(String word) {
TrieNode currentNode = root;
// Traverse the Trie for each character in the word
for (char c : word.toCharArray()) {
int index = c - 'a'; // Calculate the index (0 to 25) corresponding to the character
if (currentNode.children[index] == null) {
// If the corresponding child node does not exist, create it
currentNode.children[index] = new TrieNode();
}
// Move to the next node in the Trie
currentNode = currentNode.children[index];
}
// Mark the last node as the end of a word
currentNode.isEndOfWord = true;
}
// Method to search for a word in the Trie, including support for wildcard '.'
public boolean search(String word) {
// Start the search from the root node
return searchInNode(word, root);
}
// Helper method for recursive search in the Trie
private boolean searchInNode(String word, TrieNode node) {
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (c == '.') {
// If the character is a '.', check all possible child nodes
for (TrieNode child : node.children) {
if (child != null && searchInNode(word.substring(i + 1), child)) {
return true;
}
}
return false; // If no path matched, return false
} else {
// If the character is not '.', move to the corresponding child node
int index = c - 'a';
if (node.children[index] == null) {
return false; // Character not found in Trie
}
node = node.children[index]; // Move to the next node
}
}
// After processing all characters, return whether we are at the end of a valid word
return node.isEndOfWord;
}
}Solution in C#
C#
// Definition of TrieNode class
public class TrieNode {
public TrieNode[] Children; // Array to store child nodes for each character 'a' to 'z'
public bool IsEndOfWord; // Flag to indicate if this node marks the end of a word
public TrieNode() {
Children = new TrieNode[26]; // Initialize the array with 26 null entries (for 'a' to 'z')
IsEndOfWord = false; // By default, a node is not the end of a word
}
}
// Definition of WordDictionary class
public class WordDictionary {
private TrieNode root; // Root node of the Trie
// Constructor to initialize the root node
public WordDictionary() {
root = new TrieNode();
}
// Method to add a word to the Trie
public void AddWord(string word) {
TrieNode currentNode = root;
// Traverse the Trie for each character in the word
foreach (char c in word) {
int index = c - 'a'; // Calculate the index (0 to 25) corresponding to the character
if (currentNode.Children[index] == null) {
// If the corresponding child node does not exist, create it
currentNode.Children[index] = new TrieNode();
}
// Move to the next node in the Trie
currentNode = currentNode.Children[index];
}
// Mark the last node as the end of a word
currentNode.IsEndOfWord = true;
}
// Method to search for a word in the Trie, including support for wildcard '.'
public bool Search(string word) {
// Start the search from the root node
return SearchInNode(word, root);
}
// Helper method for recursive search in the Trie
private bool SearchInNode(string word, TrieNode node) {
for (int i = 0; i < word.Length; i++) {
char c = word[i];
if (c == '.') {
// If the character is a '.', check all possible child nodes
foreach (TrieNode child in node.Children) {
if (child != null && SearchInNode(word.Substring(i + 1), child)) {
return true;
}
}
return false; // If no path matched, return false
} else {
// If the character is not '.', move to the corresponding child node
int index = c - 'a';
if (node.Children[index] == null) {
return false; // Character not found in Trie
}
node = node.Children[index]; // Move to the next node
}
}
// After processing all characters, return whether we are at the end of a valid word
return node.IsEndOfWord;
}
}