golang刷leetcode 字符串（2）搜索推荐系统
golang刷leetcode 字符串（2）搜索推荐系统
给你一个产品数组 products 和一个字符串 searchWord ，products 数组中每个产品都是一个字符串。
请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。
请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。
示例 1：
输入：
products = ["mobile","mouse","moneypot","monitor","mousepad"],
searchWord = "mouse"输出：
[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]
示例 2：
输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
示例 3：
输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]示例 4：
输入：products = ["havana"], searchWord = "tatiana"
输出：[[],[],[],[],[],[],[]]提示：
1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。
解题思路：
1，字符串匹配的问题，一般可以用Tires树（前缀树）
2，本题的思路分两步
A，用输入的products 建立tire树
B，针对searchWord的每一个前缀，进行匹配。
C，Tire 树的前3个输入保证了字典序。
func suggestedProducts(products []string, searchWord string) [][]string {
root := &Tire{}
for i := range products {
root.Insert(products[i])
}
//root.Print(0)
var r [][]string
for i := 0; i < len(searchWord); i++ {
ri := root.Prefix(searchWord[:i+1])
if len(ri) > 3 {
ri = ri[:3]
}
r = append(r, ri)
}
return r
}
type Tire struct {
IsWord bool
Children [26]*Tire
}
//辅助函数用用于调试
func (t *Tire) Print(depth int) {
fmt.Println(depth, t)
for i := 0; i < 26; i++ {
if t.Children[i] != nil {
fmt.Println(depth, string('a'+i))
t.Children[i].Print(depth + 1)
}
}
}
//递归建立tire树，循环也可以
func (t *Tire) Insert(word string) {
if len(word) == 0 {
t.IsWord = true
return
}
index := word[0] - 'a'
if t.Children[index] == nil {
t.Children[index] = &Tire{}
}
t.Children[index].Insert(word[1:])
}
//完整单词匹配
func (t *Tire) Search(word string) bool {
if len(word) == 0 {
return t.IsWord
}
index := word[0] - 'a'
return t.Children[index].Search(word[1:])
}
//前缀匹配
func (t *Tire) Prefix(word string) []string {
cur := t
last := t
var i int
for i = 0; i < len(word); i++ {
index := word[i] - 'a'
//fmt.Println("cur", cur)
if cur != nil {
last = cur
cur = cur.Children[index]
//fmt.Println(cur)
} else {
break
}
}
//fmt.Println("cur->", cur)
var r []string
if i == 0 {
return r
}
pre := ""
if i > 1 {
pre = word[:i-1]
}
li := word[i-1] - 'a'
//fmt.Println("pre->", pre, i, word, string(word[i-1]), last.Children[li])
if last != nil && last.Children[li] != nil {
if last.Children[li].IsWord {
r = append(r, pre+string(word[i-1]))
}
csi := last.Children[li].ChildrenStr()
//fmt.Println("pre +csi", pre, string(word[i-1]), csi)
for _, c := range csi {
r = append(r, pre+string(word[i-1])+c)
}
}
return r
}
//匹配剩余部分遍历
func (t *Tire) ChildrenStr() []string {
var r []string
for i := 0; i < 26; i++ {
if t != nil && t.Children[i] != nil {
if t.Children[i].IsWord {
r = append(r, string('a'+i))
}
csi := t.Children[i].ChildrenStr()
//fmt.Println("Children", i, t.Children[i].ChildrenStr())
for _, c := range csi {
r = append(r, string('a'+i)+c)
}
}
}
return r
}https://leetcode-cn.com/problems/search-suggestions-system/
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
