Three Word Suggestions for Every Prefix
Problem statement
For every nonempty prefix of query, return up to three words that start with that prefix. Give one result row for each prefix, in increasing prefix length.
For this exercise, words are distinct, nonempty lowercase English strings. Choose the three lexicographically smallest matching words, and put each row in lexicographic order. If fewer than three words match, return all of them. If no word matches, return an empty row; keep a row for every later prefix as well.
An empty query returns an empty outer array. The input order of words does not affect the answer. This is a suggestion for every query prefix, not only the first three characters.
Function
wordSuggestions(words: String[], query: String) → String[][]Examples
Example 1
words = ["cat","carpet","car","camera","apple"]query = "camera"return = [["camera","car","carpet"],["camera","car","carpet"],["camera"],["camera"],["camera"],["camera"]]For c and ca, sorted matches are camera, car, carpet, cat, so choose camera, car, carpet. From cam through camera, only camera matches. The six rows are [["camera","car","carpet"],["camera","car","carpet"],["camera"],["camera"],["camera"],["camera"]].
Example 2
words = ["dog","door","dove"]query = "doz"return = [["dog","door","dove"],["dog","door","dove"],[]]For d and do, all three words match in order dog, door, dove. No word starts with doz, so the last row is empty.
Constraints
0 <= words.length <= 10001 <= words[i].length <= 300 <= query.length <= 30- Words are distinct and contain only lowercase English letters. Query contains only lowercase English letters.