LESSON 471 OF 637 · TRIES

Search Suggestions System in C#

Practice O(S log n + m)

You get an array of words named products, and a word named searchWord. Return the search suggestions for each letter of searchWord.

Picture someone typing searchWord into a search box, one letter at a time. After each letter, the box shows up to 3 products. They are products that start with the letters typed so far.

When more than 3 products match, show the first 3 in alphabetical order. Each list of suggestions is in alphabetical order. When no product matches, the list is empty.

Return one list per letter, in typing order.

Example 1:

Input: products = ["tomato","tea","toast","tofu","tart"], searchWord = "tof"
Output: [["tart","tea","toast"],["toast","tofu","tomato"],["tofu"]]
Explanation: After "t", all five products match.
The first three in alphabetical order are shown.
After "to", three products match.
After "tof", only "tofu" matches.

Example 2:

Input: products = ["lamp","desk","chair"], searchWord = "lens"
Output: [["lamp"],[],[],[]]
Explanation: After "l", only "lamp" matches.
No product starts with "le", so the last three lists are empty.

Example 3:

Input: products = ["cab","ca","cabin","cable"], searchWord = "cab"
Output: [["ca","cab","cabin"],["ca","cab","cabin"],["cab","cabin","cable"]]
Explanation: A word comes before the longer words that start with it.
So "ca" is first, then "cab".
After "cab", "ca" no longer matches.

Constraints:

1 to 1,000 products.
Each product has 1 to 1,000 letters.
All products together have at most 30,000 letters.
All products are different.
searchWord has 1 to 1,000 letters.
Every letter is a lowercase English letter.

Note:

Your solution should run in O(S log n + m) time. Here n is the number of products, S their total number of letters, and m the length of searchWord.

Sort the products first. Then, for any letters typed, the first 3 products that start with them are the ones to show.

Put the sorted products in a trie. Let each node keep the first 3 products whose path goes through it. Then each typed letter is one step down the trie, and the node you reach holds the suggestions.

Sorting takes O(S log n) time. Building the trie visits each letter of the products once: O(S).
Typing searchWord takes one step per letter: O(m).
The trie has at most S nodes, and each node keeps at most 3 products.

STEP 1 OF 18

Guided

Ctrl + Enter to check