DIY: Design Add and Search Words Data Structure

Problem statement

Design a data structure that supports the following functions:

• Adding new words.
• Finding if a string matches any previously added string.
• Returning all the words that are present in the data structure.

Let’s call this data structure the WordDictionary class. Here is how it should be implemented:

• __init__(): This function will initialize the object.
• add_word(word): This function will add word to the data structure so that it can be matched later.
• search(word): This function will return True if there is any string in the WordDictionary object that matches the query word. Otherwise, it will return False. If the query word contains dots ., then it should be matched with every letter. For example: . in the string ".ad" can have 26 possible search results like “aad”, “bad”, “cad”, and so on.
• get_words(): This function will return all of the words present in the WordDictionary class.

Note: You cannot add a word that is already present in the dictionary.

Input

add_word: The input for this function is the word you want to add to the word dictionary.

search: The input for this function is the word you want to search for in the word dictionary.

get_words: This function does not take any input.

Output

add_word: This function does not return any output.

search: This function returns True if the word you are looking for is present in the word dictionary. Otherwise, it returns False.

get_words: This function returns a list of all the words that are present in the word dictionary.

Coding exercise

For this coding exercise, you have to implement the WordDictionary() class. The class has four functions:

• __init__(): This is the constructor.
• add_word(word): Here word is a string that you will add to the dictionary.
• search(word): Here word is a string that you have to find in the dictionary. The function will return True if the word is present, otherwise False.
• get_words(): This function will return all of the words present in the WordDictionary class.