Pinterest Search needs to return up to k autocomplete suggestions for a lowercase prefix. Given a collection of searchable terms, build a trie and return the matching terms in lexicographic order.
Implement autocomplete(words, prefix, k). Each term may be inserted once, and suggestions must contain complete terms that start with prefix. Return fewer than k terms when fewer matches exist.
words, a list of lowercase strings; prefix, a lowercase string; and k, a positive integer.k distinct strings beginning with prefix, sorted in lexicographic order.a through z.def autocomplete(words, prefix, k):