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

文章目录

前言
LeetCode、1268. 搜索推荐系统【中等，前缀树+优先队列、排序+前缀匹配】
- 题目类型及分类
- 思路
- - API调用（排序+前缀匹配）
  - 前缀树+优先队列
资料获取

前言

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

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

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

视频平台：b站-Coder长路

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

题目类型及分类

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

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

思路

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

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

class Solution {

    //prodcuts数量2万  单词1000
    public 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<>();
            //遍历所有products
            for (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 {

    //每一个大顶堆中的数量为3
    private 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;
    }

}