1268. Search Suggestions System
Medium
You are given an array of strings
products
and a string searchWord
.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 searchWord
. If there are more than three products with a common prefix return the three lexicographically minimums products.Return a 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"]]
Explanation:
The only word "havana" will be always suggested while typing the search word.
Constraints:
1 <= products.length <= 1000
1 <= products[i].length <= 3000
1 <= sum(products[i].length) <= 2 * 104
- All the strings of
products
are unique. products[i]
consists of lowercase English letters.1 <= searchWord.length <= 1000
searchWord
consists of lowercase English letters.
Trie 的改版,如果走過的路徑的 suggest 陣列內未滿三個字串,就將目前正在插入的字串加入陣列。最後遞迴 searchWord 時將這些陣列取出。
type Trie struct {
children [26]*Trie
suggest []string
}
func (this *Trie) Insert(word string) {
for i:=0; i<len(word); i++ {
if this.children[word[i] - 'a'] == nil {
this.children[word[i] - 'a'] = &Trie{}
}
this = this.children[word[i]-'a']
if len(this.suggest) < 3 {
this.suggest = append(this.suggest, word)
}
}
}
func suggestedProducts(products []string, searchWord string) [][]string {
dic := Trie{}
res := make([][]string, 0)
for i:=0; i<len(searchWord); i++ {
res = append(res, []string{})
}
sort.Strings(products)
for _, product := range products {
dic.Insert(product)
}
d := &dic
for i:=0; i<len(searchWord); i++ {
if d.children[searchWord[i] - 'a'] == nil {
return res
}
d = d.children[searchWord[i]-'a']
res[i] = d.suggest
}
return res
}