1. 问题描述：
给你一个产品数组 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 中所有字符都是小写英文字母。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-suggestions-system
2. 思路分析：
① 对于这种问题的比较常规的方法是使用字典树来进行解决，我们在循环遍历这些products单词的时候就创建字典树，所以我们通过当前的单词构建字典树的时候需要遍历当前单词的所有字母，通过单词中的字母可以看成是前缀来完善字典树，对于字典树我们可以通过简单的例子来画出具体的字典树这样会更好理解一点，下面是products = ["abc", "abd", "abf"]， searchWord = "abf"的构建出来的字典树
② 其实画出对应的字典树，并且在循环中更新当前的根节点那么就可以不断完善出字典树，最后我们只需要遍历出字典树中对应的单词即可
3. 代码如下：
下面是官方提供的代码（自己做了一些注释）
class Trie: # 相当于Java中的构造器调用这个函数返回的是这个对象 def __init__(self): self.child = dict() self.words = list() class Solution: def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]: # 这道题目可能与之前有不同的思路, 值得学习一下 可以使用字典树进行解决 # 可以画出具体的一棵树来进行理解 def addWord(root, word): cur = root for ch in word: if ch not in cur.child: cur.child[ch] = Trie() # 下一次循环的时候当前的孩子为根, 所以需要修改的根为当前的孩子节点 cur = cur.child[ch] cur.words.append(word) cur.words.sort() if len(cur.words) > 3: cur.words.pop() # 返回的是一个对象来的 root = Trie() for word in products: addWord(root, word) # 使用list函数创建一个空的list列表 ans = list() cur = root # 设计标记的目的是为了在第一个字母不匹配的时候直接创建空列表即可 flag = False for ch in searchWord: if flag or ch not in cur.child: ans.append(list()) flag = True else: cur = cur.child[ch] ans.append(cur.words) return ans
