Practice/Meta/Leetcode 1268. Search Suggestions System

Leetcode 1268. Search Suggestions System

CodingOptional

Problem

You are building an autocomplete feature for an e-commerce search bar. Given a list of product names and a search query that a user is typing character by character, return suggestions for each prefix of the search query.

For each prefix (formed by typing the search word one character at a time from left to right), return up to three product names that:

• Start with that prefix
• Are lexicographically smallest among all matching products

Return a list of suggestion lists, one for each character typed in the search word.

Requirements

1. Return suggestions for every prefix of searchWord (from the first character to the complete word)
2. For each prefix, return at most 3 product names that start with that prefix
3. The suggested products must be sorted lexicographically
4. If fewer than 3 products match a prefix, return all matching products
5. If no products match a prefix, return an empty list for that position

Constraints

• 1 ≤ products.length ≤ 1000
• 1 ≤ products[i].length ≤ 3000
• 1 ≤ searchWord.length ≤ 1000
• All strings consist of lowercase English letters only
• All product names are unique

Examples

Example 1:

` Input: products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"] searchWord = "mouse"

Output: [ ["mobile", "moneypot", "mouse"], ["mouse", "mousepad"], ["mouse", "mousepad"], ["mouse", "mousepad"], ["mouse", "mousepad"] ]

Explanation:

• Prefix "m": matches mobile, mouse, moneypot, monitor, mousepad → return first 3 alphabetically
• Prefix "mo": matches mouse, moneypot, monitor, mousepad → return first 3 alphabetically
• Prefix "mou": matches mouse, mousepad → return both
• Prefix "mous": matches mouse, mousepad → return both
• Prefix "mouse": matches mouse, mousepad → return both `

Example 2:

` Input: products = ["havana"] searchWord = "tatiana"

Output: [[], [], [], [], [], [], []]

Explanation: No products start with 't', so all prefixes return empty lists. `

Example 3:

` Input: products = ["code", "coder", "coding", "codable", "codec", "codecs", "coded", "codes"] searchWord = "code"

Output: [ ["code", "codable", "codec"], ["code", "codable", "codec"], ["code", "codable", "codec"], ["code", "codable", "codec"] ]

Explanation: For each prefix of "code", the first 3 alphabetically are: code, codable, codec. `