1268. Search Suggestions System #

Problem #

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Constraints:

• 1 <= products.length <= 1000
• There are no repeated elements in products.
• 1 <= Σ products[i].length <= 2 * 10^4
• All characters of products[i] are lower-case English letters.
• 1 <= searchWord.length <= 1000
• All characters of searchWord are lower-case English letters.

Problem Summary #

Given a product array products and a string searchWord, where each product in the products array is a string. Please design a recommendation system that, after each letter of the word searchWord is typed in sequence, recommends at most three products from the products array whose prefix is the same as searchWord. If there are more than three recommendable products with the same prefix, return the three smallest in lexicographical order. Return, in the form of a two-dimensional list, the corresponding list of recommended products after each letter of searchWord is typed.

Solution Approach #

• Since the problem requires the returned answer to be output in lexicographical order, sort first. Ordered strings also satisfy the conditions for binary search, so binary search can be used. sort.SearchStrings returns the first starting index that satisfies the search condition. Strings at the end that do not satisfy the condition need to be cut off. Therefore, search 2 times: the first binary search filters out strings that do not satisfy the target string prefix. The second binary search then finds the strings that ultimately satisfy the problem requirements.

Code #

package leetcode

import (
	"sort"
)

func suggestedProducts(products []string, searchWord string) [][]string {
	sort.Strings(products)
	searchWordBytes, result := []byte(searchWord), make([][]string, 0, len(searchWord))
	for i := 1; i <= len(searchWord); i++ {
		searchWordBytes[i-1]++
		products = products[:sort.SearchStrings(products, string(searchWordBytes[:i]))]
		searchWordBytes[i-1]--
		products = products[sort.SearchStrings(products, searchWord[:i]):]
		if len(products) > 3 {
			result = append(result, products[:3])
		} else {
			result = append(result, products)
		}
	}
	return result
}