leetcode1268_go_搜索推荐系统

题目

给你一个产品数组 products 和一个字符串 searchWord ，products 数组中每个产品都是一个字符串。

请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。

如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。

请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

示例 1：输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

输出：[

["mobile","moneypot","monitor"],

["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、排序；时间复杂度O(n^2)，空间复杂度O(n^2)

func suggestedProducts(products []string, searchWord string) [][]string {
   sort.Strings(products)
   res := make([][]string, 0)
   for i := 0; i < len(searchWord); i++ {
      target := searchWord[:i+1]
      arr := make([]string, 0)
      for j := 0; j < len(products); j++ {
         if len(products[j]) >= len(target) && products[j][:i+1] == target {
            arr = append(arr, products[j])
         }
         if len(arr) == 3 {
            break
         }
      }
      res = append(res, arr)
   }
   return res
}

2、trie树；时间复杂度O(n^2)，空间复杂度O(n^2)

func suggestedProducts(products []string, searchWord string) [][]string {
   res := make([][]string, len(searchWord))
   t := &Trie{}
   for i := 0; i < len(products); i++ {
      t.Insert(products[i])
   }
   for i := 0; i < len(searchWord); i++ {
      res[i] = t.StartsWith(searchWord[:i+1])
   }
   return res
}

type Trie struct {
   next [26]*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
   str  string
}

// 插入word
func (this *Trie) Insert(word string) {
   temp := this
   for _, v := range word {
      value := v - 'a'
      if temp.next[value] == nil {
         temp.next[value] = &Trie{
            next: [26]*Trie{},
         }
      }
      temp = temp.next[value]
   }
   temp.str = word
}

// 查找前缀
func (this *Trie) StartsWith(prefix string) []string {
   temp := this
   for _, v := range prefix {
      value := v - 'a'
      if temp = temp.next[value]; temp == nil {
         return nil
      }
   }
   res := make([]string, 0)
   temp.dfs(&res)
   return res
}

func (this *Trie) dfs(res *[]string) {
   if len(*res) == 3 {
      return
   }
   if this.str != "" {
      *res = append(*res, this.str)
   }
   for _, v := range this.next {
      if len(*res) == 3 {
         return
      }
      if v == nil {
         continue
      }
      v.dfs(res)
   }
}