1268. 搜索推荐系统 Medium
给你一个产品数组 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"
输出：[[],[],[],[],[],[],[]]
解题思路
输入：一个产品数组 products 和一个字符串 searchWord
输出：设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品
本题属于 前缀树 Trie 问题。
解法 1：排序 + 遍历（暴力法）
- 先对
products排序。 - 每次取前缀
prefix，遍历所有产品，找出前 3 个startsWith(prefix)的单词。 - 时间复杂度较高：
O(m * n)（m = searchWord.length, n = 产品数）。 👉 实现简单，但效率不高。
解法 2：排序 + 二分查找（推荐 ✅）
- 对
products排序。 - 每次取前缀
prefix，用 二分查找 找到第一个>= prefix的位置。 - 从该位置向后取最多 3 个单词，检查是否匹配前缀。
- 时间复杂度：
O(n log n + m log n)，效率比暴力好很多。 👉 代码实现简洁，性能好，面试友好。
解法 3：Trie 前缀树（适合高频查询）
- 构建 Trie，每个节点存储该前缀下最多 3 个字典序最小的产品。
- 插入时，因为
products已经排过序，所以插入过程中只需要保留前 3 个候选。 - 查询时，沿着
searchWord逐个字符遍历 Trie，取出对应节点的suggestions。 - 时间复杂度：
- 构建 Trie：
O(n * L)（n = 产品数，L = 单词长度） - 查询：
O(m)（m = searchWord.length） 👉 更偏 算法题风格，适合大量查询场景。
- 构建 Trie：
🔹 总结
- 暴力法：实现最简单，效率低。
- 二分查找法：代码简洁，效率高，面试中常用。
- Trie 法：适合算法题和高频查询，空间换时间。
代码实现
class TrieNode:
def __init__(self):
# 子节点：key = 字符, value = TrieNode
self.children = {}
# 当前前缀下的推荐词（最多 3 个）
self.suggestions = []
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
"""向 Trie 中插入一个单词"""
node = self.root
for ch in word:
# 如果没有该字符，创建一个子节点
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
# 在当前节点维护推荐列表（只保留前 3 个，已排序）
if len(node.suggestions) < 3:
node.suggestions.append(word)
def getSuggestions(self, prefix: str) -> List[List[str]]:
"""根据搜索前缀返回推荐结果"""
node = self.root
res = []
for ch in prefix:
if node and ch in node.children:
node = node.children[ch]
res.append(node.suggestions)
else:
# 如果某个前缀不存在，后续所有前缀都返回 []
node = None
res.append([])
return res
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
# 先排序，保证字典序最小的先插入 Trie
products.sort()
trie = Trie()
# 插入所有产品
for p in products:
trie.insert(p)
# 查询推荐结果
return trie.getSuggestions(searchWord)class TrieNode {
constructor() {
this.children = new Map(); // 子节点
this.suggestions = []; // 推荐的单词（最多 3 个）
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
// 插入单词
insert(word) {
let node = this.root;
for (let ch of word) {
if (!node.children.has(ch)) {
node.children.set(ch, new TrieNode());
}
node = node.children.get(ch);
// 在当前节点维护推荐列表（最多 3 个）
if (node.suggestions.length < 3) {
node.suggestions.push(word);
}
}
}
// 查询前缀推荐结果
getSuggestions(prefix) {
let node = this.root;
const res = [];
for (let ch of prefix) {
if (node && node.children.has(ch)) {
node = node.children.get(ch);
res.push(node.suggestions);
} else {
// 前缀不存在，后面都只能返回 []
node = null;
res.push([]);
}
}
return res;
}
}
var suggestedProducts = function(products, searchWord) {
// 先排序，保证插入 Trie 时字典序正确
products.sort();
// 构建 Trie
const trie = new Trie();
for (let word of products) {
trie.insert(word);
}
// 查询前缀建议
return trie.getSuggestions(searchWord);
};
// 二分法解决 O(n log n + m log n)
// var suggestedProducts = function(products, searchWord) {
// // 先对商品列表按字典序排序
// products.sort();
// const res = [];
// let prefix = '';
// // 遍历搜索词的每个字符，逐步形成前缀
// for (let ch of searchWord) {
// prefix += ch;
// // 二分查找，找到第一个 >= prefix 的位置
// let l = 0;
// let r = products.length;
// while (l < r) {
// const mid = Math.floor((l + r) / 2);
// // 如果中间元素比 prefix 小，说明答案在右边
// if (products[mid] < prefix) {
// l = mid + 1;
// } else {
// // 否则收缩右边界
// r = mid;
// }
// }
// // 从二分查找到的位置开始，最多取 3 个商品
// const temp = [];
// for (let i = l; i < Math.min(l + 3, products.length); i++) {
// // 必须满足前缀匹配
// if (products[i].startsWith(prefix)) {
// temp.push(products[i]);
// }
// }
// // 保存当前前缀的推荐结果
// res.push(temp);
// }
// return res;
// };复杂度分析
时间复杂度：O(n * L)
空间复杂度：O(m)