Problem · Trie
Search Suggestions with a Prefix Tree
Learn this problem● Medium
CitadelINTERNONSITE INTERVIEW
CitadelINTERNONSITE INTERVIEWProblem statement
You are given an array of distinct lowercase product names products and a lowercase search string query.
After each character of query is typed, form the accumulated non-empty prefix and return up to three product names that begin with that prefix.
- Order matching products lexicographically.
- If more than three products match, keep the first three.
- Once a prefix has no matches, that prefix and every longer prefix return an empty list.
Return one suggestion list for every character of query, in order.
Function
searchSuggestions(products: String[], query: String) → String[][]Examples
Example 1
products = ["mobile","mouse","moneypot","monitor","mousepad"]query = "mouse"return = [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]The first two prefixes are m and mo, whose first three lexicographic matches are mobile, moneypot, and monitor. From mou onward, only mouse and mousepad match.
Example 2
products = ["bags","baggage","banner","box","cloths"]query = "bags"return = [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]The prefixes b and ba have at least three matches. Prefix bag has two matches, and the full prefix bags has one.
Example 3
products = ["alpha","alpine","beta"]query = "cat"return = [[],[],[]]No product begins with c, so every prefix returns an empty list.
Constraints
1 <= products.length <= 100000.- Every product is a distinct non-empty lowercase English string.
1 <= query.length <= 100000.- The total number of characters across all products is at most
10^6.