Feature #1: Store and Fetch Words

Description

For the first feature, your company wants you to design a module for the search engine that can be used to store and fetch words efficiently. This module will act as a dictionary with insert and search functionalities. Moreover, this dictionary should also have a feature for searching whether a given prefix exists in the dictionary or not. This feature can be represented by the startsWith function because a prefix comes at the beginning of the word.

Let’s say we insert the following words in the dictionary: the, a, there, answer, any, by, bye, their, and abc by calling the insert() function. Then, by calling the search() function with input, there should return true. Similarly, calling the starts_with() function with the prefix by should also return true.