Autocomplete Words by Prefix Using Trie

Problem: Autocomplete Words by Prefix Given an array of strings words and multiple query strings prefix, return all words in words that start with each queried prefix. To make the output deterministic, return the matched words in ascending lexicographical order for each query. If no word matches a query, output an empty line. Input Format n q word_1 word_2 ... word_n prefix_1 prefix_2 ... prefix_q n is the number of words. q is the number of queries. The next n lines contain one word each. The next q lines contain one query prefix each. Output Format Print q lines. For each query: If there are matched words, print them in ascending lexicographical order separated by spaces. If there is no match, print an empty line. Constraints 1 <= n <= 2 * 10^5 1 <= q <= 2 * 10^5 1 <= len(word_i), len(prefix_i) <= 100 All word_i and prefix_i contain only lowercase English letters a-z. sum(len(word_i)) + sum(len(prefix_i)) <= 2 * 10^5 The total output size is reasonable. Example Input: 5 4 apple app application banana band app ban bana cat Output: app apple application banana band banana Example Input 5 4 apple app application banana band app ban bana cat Output app apple application banana band banana