Autocomplete Suggestions for Restaurant Search
Zomato's success heavily relies on its intuitive user experience, especially in search. When a user starts typing a restaurant name, providing instant, accurate autocomplete suggestions significantly enhances usability. This problem challenges you to implement a core component of such a system using a Trie data structure, enabling efficient prefix-based searches for restaurant names.
Your task is to implement the RestaurantSearchTrie class, which supports the following operations:
constructor(): Initializes the Trie data structure.insert(word: string): Inserts a word (restaurant name) into the Trie.search(word: string): Returns true if the word is in the Trie, and false otherwise.startsWith(prefix: string): Returns true if there is any word in the Trie that starts with the given prefix, and false otherwise.insert(word: string): Takes a string word representing a restaurant name. This method does not return anything.search(word: string): Takes a string word. Returns a boolean.startsWith(prefix: string): Takes a string prefix. Returns a boolean.word and prefix inputs will consist of lowercase English letters (a-z).search or startsWith behavior).word or prefix is not expected as input.Examples
Example 1
Input:
operations = ["RestaurantSearchTrie", "insert", "insert", "search", "search", "startsWith", "startsWith", "insert", "startsWith"], params = [[], ["pizza"], ["pizzeria"], ["pizza"], ["pizzaria"], ["piz"], ["burg"], ["burger"], ["burg"]]
Output:
[null, null, null, true, false, true, false, null, true]
Note:
Example 2
Input:
operations = ["RestaurantSearchTrie", "insert", "search", "startsWith"], params = [[], ["food"], ["food"], ["fo"]]
Output:
[null, null, true, true]
Note:
Constraints
insert operations will not exceed 3000.search and startsWith operations will not exceed 10^4.word or prefix will be between 1 and 20 characters.insert, search, and startsWith should be optimal (proportional to the length of the input string).insert, search, and startsWith.Loading editor...