Implement Store Autocomplete

Problem Statement

You are tasked with building a backend service for an autocomplete feature that suggests store names as a user types. Given a fixed list of store_names, implement a class AutocompleteSystem that provides efficient lookup for all store names starting with a given prefix.

Requirements

• Implement the __init__(self, store_names) method to store the initial list.
• Implement the search(self, prefix) method, which returns a list of all store names that start with the provided prefix.
• If multiple stores match, return them in lexicographical (alphabetical) order.

Function Signature

class AutocompleteSystem:
    def __init__(self, store_names: list[str]):
        # Initialize data structure

    def search(self, prefix: str) -> list[str]:
        # Return sorted list of matching stores

Examples

Example 1: Input: store_names = ["Burger King", "Burger Queen", "Pizza Hut", "Blueberry Cafe"], prefix = "Bur" Output: ["Burger King", "Burger Queen"]

Example 2: Input: store_names = ["Apple Store", "Applebee's", "Apricot"], prefix = "App" Output: ["Apple Store", "Applebee's"]

Constraints

• Number of store names: up to 10,000.
• Length of each store name: up to 50 characters.
• prefix length: 1 to 50 characters.
• The system should prioritize fast search execution.