You are building a restaurant search engine for DoorDash using a trie (prefix tree).

You are given an initial list of restaurant names such as ["panda express", "panera bread"]. Each restaurant name must be stored so that you can:

• insert a new restaurant name,
• check whether an exact restaurant name exists,
• check whether any stored restaurant name starts with a given prefix,
• return up to k restaurant names that start with a given prefix.

The search engine stores only unique restaurant names. If the same restaurant name appears multiple times in the constructor input or is inserted multiple times later, it is still stored only once.

If fewer than k restaurant names match the prefix, return all matching names. If no restaurant name matches the prefix, return an empty list.

Returned restaurant names must be sorted in lexicographically ascending order.

Class to Implement

Implement the RestaurantSearchEngine class.

Method Signatures

Constructor

RestaurantSearchEngine(List<String> restaurantNames)

• Initializes the search engine with the given list of restaurant names.
• Each restaurant name in restaurantNames should be inserted.
• Duplicate names in restaurantNames should be stored only once.
• If the input list is empty, the search engine starts with no restaurant names.

Insert Restaurant

void insertRestaurant(String restaurantName)

• Inserts restaurantName into the search engine.
• If restaurantName is already stored, this call does nothing.

Check Exact Restaurant

boolean containsRestaurant(String restaurantName)

• Returns true if restaurantName is currently stored.
• Returns false otherwise.

Check Prefix

boolean startsWith(String prefix)

• Returns true if there is at least one stored restaurant name that starts with prefix.
• Returns false otherwise.

Get Matching Restaurants

List<String> getTopKRestaurants(String prefix, int k)

• Returns up to the lexicographically smallest k stored restaurant names that start with prefix.
• If fewer than k restaurant names match, return all matching restaurant names.
• If no restaurant name matches, return an empty list.

Input Rules

• Each restaurant name contains only lowercase English letters and single spaces.
• A restaurant name does not start or end with a space.
• A restaurant name does not contain consecutive spaces.
• Each prefix contains only lowercase English letters and spaces.
• A prefix does not start or end with a space.
• A prefix does not contain consecutive spaces.
• An empty prefix is not allowed.
• The trie must treat the space character as a valid stored character.

Constraints

• 0 ≤ restaurantNames.size() ≤ 3 * 104
• 1 ≤ restaurantName.length() ≤ 2000
• 1 ≤ prefix.length() ≤ 2000
• 1 ≤ k ≤ 3 * 104
• At most 3 * 104 total calls will be made to insertRestaurant, containsRestaurant, startsWith, and getTopKRestaurants.

Examples

Example 1

Example 2

Example 3

Example 4