Lexicographic Search Suggestions
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
Given unique lowercase product names and a lowercase searchWord, return suggestions after each character of searchWord is typed.
For every non-empty prefix, return at most three products that start with that prefix. Choose the three lexicographically smallest matching names and list them in ascending lexicographic order.
If no product matches a prefix, return an empty list for that prefix and every longer prefix.
Function
suggestedProducts(products: String[], searchWord: String) → String[][]Examples
Example 1
products = ["mobile","mouse","moneypot","monitor","mousepad"]searchWord = "mouse"return = [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]The first two prefixes have at least three matches. From prefix mou onward, only mouse and mousepad remain.
Example 2
products = ["havana"]searchWord = "havana"return = [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]The only product matches every typed prefix.
Example 3
products = ["bags","baggage","banner","box","cloths"]searchWord = "bags"return = [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]Each longer prefix narrows the lexicographically sorted matching range.
Constraints
1 <= products.length <= 100000.- Product names are unique lowercase English strings.
1 <= products[i].length <= 100.1 <= searchWord.length <= 1000, and it contains lowercase English letters.- The total number of product characters is at most
500000.