Search Autocomplete With Top Suggestions
Problem statement
Build a small search-box autocomplete. It starts empty and supports two calls:
search(query): someone searched forquery. Add 1 to that query's search count.suggest(prefix): return at most 3 past queries that start withprefix.
Rules for suggest:
- Queries with more searches come first.
- Queries with the same count come in alphabetical order, comparing character by character by character code. A space comes before every letter, and a shorter query comes before a longer one that starts with it.
- A query that is exactly equal to
prefixcounts as starting with it. - If fewer than 3 queries match, return all of them; if none match, return an empty list.
- Calling
suggestdoes not count as a search.
You get the calls in order as two arrays: operations[i] is "search" or "suggest", and texts[i] is its query or prefix. Return one list for each suggest call, in the order the calls were made.
Function
runAutocomplete(operations: String[], texts: String[]) → List<List<String>>Examples
Example 1
operations = ["search","search","search","search","suggest","search","search","suggest","suggest"]texts = ["photo editor","photoshop","photoshop","photo","pho","photo editor","photo editor","photo","photos"]return = [["photoshop","photo","photo editor"],["photo editor","photoshop","photo"],["photoshop"]]At the first "pho" suggestion, "photoshop" has been searched twice and the other two once each. So it comes first, then the tie between "photo" and "photo editor" is broken alphabetically: "photo" is a prefix of the other, so it comes first. After two more searches of "photo editor" (3 in total), it leads the "photo" list. Only "photoshop" starts with "photos".
Example 2
operations = ["search","search","search","search","suggest","suggest"]texts = ["cat","car","cab","cap","ca","dog"]return = [["cab","cap","car"],[]]All four queries were searched once, so the alphabetical order decides: "cab", "cap", "car", and "cat" is dropped because only 3 are shown. Nothing starts with "dog", so that list is empty.
Example 3
operations = ["search","suggest"]texts = ["pdf","pdf"]return = [["pdf"]]A query counts as starting with itself, so the single search "pdf" is suggested for the prefix "pdf".
Constraints
1 <= operations.length <= 2000andtexts.length == operations.length.- Each
operations[i]is"search"or"suggest". 1 <= texts[i].length <= 20texts[i]contains only lowercase English letters and spaces. A searched query does not start or end with a space and has no two spaces in a row.