LeetCode、1268. 搜索推荐系统【中等，前缀树+优先队列、排序+前缀匹配】

前言

博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引：博客目录索引(持续更新)

视频平台：b站-Coder长路

---

LeetCode、1268. 搜索推荐系统【中等，前缀树+优先队列、排序+前缀匹配】

题目类型及分类

题目链接：LeetCode、1268. 搜索推荐系统

分类：02数据结构/树/字典树(前缀树)

---

思路

API调用（排序+前缀匹配）

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

class Solution {//prodcuts数量2万  单词1000public List<List<String>> suggestedProducts(String[] products, String searchWord) {//根据字典序排序Arrays.sort(products);//初始化结果集合List<List<String>> ans = new ArrayList<>();//遍历所有的搜索文字for (int i = 0; i < searchWord.length(); i ++) {String s = searchWord.substring(0, i + 1);//结果集合List<String> res = new ArrayList<>();//遍历所有productsfor (String product: products) {if (product.startsWith(s)) {res.add(product);}//若是已经收集到3个if (res.size() == 3) {break;}}ans.add(res);}return ans;}
}

---

前缀树+优先队列

使用大顶堆目的：每个单词只留下3个最小字典序的，因为一旦大顶堆中有>目标数量时，就会将最大的排除出去。

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

class Solution {//每一个大顶堆中的数量为3private static final int size = 3;//根节点private TrieNode root = new TrieNode();//自定义Node节点class TrieNode {public static final int num = 26;TrieNode[] children;boolean isEnd;PriorityQueue<String> queue;public TrieNode() {this.children = new TrieNode[num];this.queue = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));}}//插入一个产品名称到前缀树public void insert(String product) {//拿到当前的前缀树节点TrieNode node = this.root;//遍历整个名称字符for (char ch: product.toCharArray()) {int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new TrieNode();}node = node.children[index];//当前节点要将单词添加进来node.queue.offer(product);if (node.queue.size() > size) {node.queue.poll();}}node.isEnd = true;}public List<List<String>> suggestedProducts(String[] products, String searchWord) {List<List<String>> ans = new ArrayList<>();//遍历所有的商品名称，依次添加到前缀树中for (String product: products) {insert(product);}//搜索所有的匹配结果TrieNode node = this.root;for (char ch: searchWord.toCharArray()) {int index = ch - 'a';//临时保存一个集合List<String> tmp = new ArrayList<>();            if (node == null) {ans.add(tmp);continue;}node = node.children[index];//节点不为空情况while (node != null && !node.queue.isEmpty()) {tmp.add(node.queue.poll());}//将整个集合翻转Collections.reverse(tmp);//添加到最终的结果集合中ans.add(tmp);}return ans;}}

---

资料获取

大家点赞、收藏、关注、评论啦~

精彩专栏推荐订阅：在下方专栏👇🏻

• 长路-文章目录汇总（算法、后端Java、前端、运维技术导航）：博主所有博客导航索引汇总
• 开源项目Studio-Vue—校园工作室管理系统(含前后台，SpringBoot+Vue)：博主个人独立项目，包含详细部署上线视频，已开源
• 学习与生活-专栏：可以了解博主的学习历程
• 算法专栏：算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻，🍅文末获取开发资源及更多资源博客获取🍅

---

整理者：长路 时间：2024.2.13