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:

• WordDictionary(): This function will initialize the object.
• void addWord(word): This function will add word to the data structure so that it can be matched later.
• bool 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.
• std::vector<std::string> getWords(): 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.