Design Add and Search Words Data Structure
Leetcode Daily Challenge (19th March, 2023)
Problem Statement:-
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.
Link: https://leetcode.com/problems/design-add-and-search-words-data-structure/
Problem Explanation with examples:-
Example 1
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 <= 25wordinaddWordconsists of lowercase English letters.wordinsearchconsist of'.'or lowercase English letters.There will be at most
3dots inwordforsearchqueries.At most
10<sup>4</sup>calls will be made toaddWordandsearch.
Intuition:-
A trie can be used to store the words in an efficient manner.
A trie is a tree data structure where each node represents a character in the word. One node can have multiple children. Each node can have a boolean variable to indicate if the word ends at that node.
A separate function can be used to perform the dfs search on the trie.
The dfs function can be used to search for the word in the trie by traversing the trie based on the characters in the word.
If the character is a '.', the function can be called recursively on all the children of the current node - backtracking.
If the character is not a '.', the function can be called recursively on the child corresponding to the character.
If the word is found, return True. Else, return False.
Solution:-
Create a trie node class with a dictionary to store the children and a boolean variable to indicate if the word ends at that node.
In the constructor of dictionary, create a root TrieNode object and assign it to the object.
Create a function to add a word to the trie. Create a current node variable and assign it to the root node.
Iterate through the characters in the word. If the character is not in the children of the current node, create a new TrieNode object and assign it to the character in the children of the current node.
Assign the current node to the child corresponding to the character.
After the iteration, set the is_word variable of the current node to True to indicate that the word ends at that node.
Create a function to search for a word in the trie. Create a dfs function that takes the root node and the index of the character in the word as parameters.
Create a current node variable and assign it to the root node.
Iterate through the characters in the word starting from the index. If the character is a '.', iterate through the children of the current node. Call the dfs function recursively on each child and the index + 1. If the dfs function returns True, return True. Else, return False.
If the character is not a '.', check if the character is in the children of the current node. If not, return False. Else, assign the current node to the child corresponding to the character.
After the iteration, return the
is_wordvariable of the current node.Call the dfs function on the root node and 0 and return the result.
Code:-
JAVA Solution
class TrieNode {
Map<Character, TrieNode> children;
boolean isWord;
TrieNode() {
children = new HashMap<>();
isWord = false;
}
}
class WordDictionary {
TrieNode root;
WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
TrieNode curr = root;
for (char ch : word.toCharArray()) {
if (!curr.children.containsKey(ch)) {
curr.children.put(ch, new TrieNode());
}
curr = curr.children.get(ch);
}
curr.isWord = true;
}
public boolean search(String word) {
return dfs(root, word, 0);
}
private boolean dfs(TrieNode curr, String word, int index) {
if (index == word.length()) {
return curr.isWord;
}
char ch = word.charAt(index);
if (ch == '.') {
for (TrieNode child : curr.children.values()) {
if (dfs(child, word, index + 1)) {
return true;
}
}
return false;
} else if (!curr.children.containsKey(ch)) {
return false;
} else {
return dfs(curr.children.get(ch), word, index + 1);
}
}
}
Python Solution
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
current_node = self.root
for character in word:
if character not in current_node.children:
current_node.children[character] = TrieNode()
current_node = current_node.children[character]
current_node.is_word = True
def search(self, word):
def dfs(root, index):
curr = root
for i in range(index,len(word)):
ch = word[i]
if ch == '.':
for child in curr.children.values():
if dfs(child,i + 1):
return True
return False
else:
if ch not in curr.children:
return False
curr = curr.children[ch]
return curr.is_word
return dfs(self.root, 0)
Complexity Analysis:-
TIME:-
addWord: O(n), where n is the length of the word being added since we iterate over each character in the word and perform a constant amount of work for each character.search: O(n * k), where n is the length of the word being searched and k is the number of children of each node in the trie. In the worst case, we have to explore every possible path through the trie, which would require iterating over every child node at each level. The '.' wildcard character in a search increases the number of possible paths to explore.
SPACE:-
addWord: O(n), where n is the length of the word being added since we create a new TrieNode for each character in the word.search: O(n), where n is the length of the word being searched since the recursive call stack will have a maximum depth of n. The space used by the TrieNodes is not considered here, since it is shared by all searches and thus its maximum size is determined by the total number of words added to the trie.