Solution: Design Add and Search Words Data Structure
Understand how to design and implement a WordDictionary that supports adding words and searching with wildcards using a trie data structure. Explore the difference between naive hash map and optimized trie approaches, their time and space complexity, and how trie nodes represent characters to enable efficient lookups in coding interviews.
We'll cover the following...
Statement
Design a data structure called WordDictionary that supports the following functionalities:
-
Constructor: This function will initialize the object.
-
Add Word(word): This function will store the provided word in the data structure.
-
Search Word(word): This function will return TRUE if any string in the WordDictionary object matches the query word. Otherwise, it will return FALSE. If the query word contains dots,
., each dot is free to match any letter of the alphabet.For example, the dot in the string “.ad” can have possible search results like “aad”, “bad”, “cad”, and so on.
-
Get Words(): This function will return all the words in the WordDictionary class.
Constraints:
-
word.length -
Words passed to Add Word() consist of lowercase English letters.
-
Words passed to Search Word() consist of
.or lowercase English letters. -
There will be, at most, three dots in a word passed to Search Word().
-
At most, ...