Simplified Autocomplete System

Implement a simplified autocomplete system. There is a database of strings, and the task is to return possible autocomplete suggestions for a given input prefix. Consider that the input may be a partial or complete word. Implement the following functionalities: add(word: str): Add a new word to the database. search(prefix: str) -> List[str]: Return a list of words that match the given prefix. Requirements: The database can contain up to 10^4 words. Each word length does not exceed 10. The input prefix length does not exceed 10. Test cases: autocomplete = AutocompleteSystem() autocomplete.add("apple") autocomplete.add("app") autocomplete.add("ape") autocomplete.add("bat") assert autocomplete.search("ap") == ["apple", "app", "ape"] assert autocomplete.search("ba") == ["bat"] assert autocomplete.search("b") == ["bat"] Example Input add apple add app add ape add bat ap ba b