Word Prefix Suggestion using Trie

microsoft Implement a simple word prefix suggestion system using a Trie data structure. Given an input prefix, return all words containing that prefix. Your implementation needs to support both adding new words and querying prefixes. Example 1: Input: add("apple"), add("app"), add("apricot"), query("ap") Output: ["apple", "app", "apricot"] Constraints: The time complexity for each query or addition can reach O(k), where k is the length of the word. The maximum number of words is 10^5. Hint: You might need to define a TrieNode class to represent each node. Example Input add("apple"), add("app"), add("apricot"), query("ap")