935. Typing Suggestions
A shop's search box suggests products while the customer types. You are given the catalogue products (names may repeat) and the finished query searchWord.
Return one list for every non-empty prefix of searchWord, from length 1 up to the full word. The list for a prefix contains up to three catalogue names that start with that prefix, in ascending lexicographic order; a name that occurs several times in the catalogue is listed once per occurrence. If fewer than three names match, list all of them, and if none match the list is empty. Sorting the catalogue once and using binary search (or a trie) is expected: aim for O(n log n) total time.
Example 1
- Input:
- products = ["mouse","mousepad","monitor","mousetrap","mouth","motor"]searchWord = "mous"
- Output:
- [["monitor","motor","mouse"],["monitor","motor","mouse"],["mouse","mousepad","mousetrap"],["mouse","mousepad","mousetrap"]]
- Explanation:
For
mandmothe three smallest names are monitor, motor, mouse; formouandmousthey are mouse, mousepad, mousetrap.
Example 2
- Input:
- products = ["lime","lemon","lychee"]searchWord = "plum"
- Output:
- [[],[],[],[]]
- Explanation:
No product starts with
p, so every entry is empty.
Example 3
- Input:
- products = ["sky","sky","skyline","ski","skate"]searchWord = "sky"
- Output:
- [["skate","ski","sky"],["skate","ski","sky"],["sky","sky","skyline"]]
- Explanation:
Duplicates are listed once per occurrence: for
skythe matches are sky, sky, skyline.
Constraints
1 ≤ products.length ≤ 105
1 ≤ products[i].length ≤ 30, 1 ≤ searchWord.length ≤ 100
All strings consist of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n * L)
- Space
- O(n)