LeetCode_前缀树_中等_1268.搜索推荐系统

这篇具有很好参考价值的文章主要介绍了LeetCode_前缀树_中等_1268.搜索推荐系统。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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 * 104
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。

2.思路

(1)前缀树
思路参考本题官方题解。文章来源地址https://www.toymoban.com/news/detail-571194.html

3.代码实现(Java)

//思路1————前缀树
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie trie = new Trie();
        for (String product : products) {
            trie.insert(product);
        }
        return trie.startWith(searchWord);
    }
}

class Trie {
    public static final int NUM = 26;
    public static final int SIZE = 3;
    Trie[] children;
    PriorityQueue<String> queue;

    public Trie() {
        children = new Trie[NUM];
        /*
			s1.compareTo(s1) 方法是用于比较字符串 s1、s2 的字典顺序的方法。它返回一个整数,表示两个字符串的相对顺序:
			(1) 如果返回值为 0,则表示两个字符串相等;
			(2) 如果返回值小于 0,则表示字符串 s1 小于 s2;
			(3) 如果返回值大于 0,则表示字符串 s1 大于 s2;
			例如,"def".compareTo("abc") 的返回值为 3
		*/
        queue = new PriorityQueue<>((p1, p2) -> p2.compareTo(p1));
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
            node.queue.offer(word);
            if (node.queue.size() > SIZE) {
                node.queue.poll();
            }
        }
    }

    public List<List<String>> startWith(String word) {
        Trie node = this;
        boolean exist = true;
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (!exist || node.children[index] == null) {
                exist = false;
                res.add(new ArrayList<>());
                continue;
            }
            node = node.children[index];
            List<String> tmp = new ArrayList<>();
            while (!node.queue.isEmpty()) {
                tmp.add(node.queue.poll());
            }
            Collections.reverse(tmp);
            res.add(tmp);
        }
        return res;
    }
}

到了这里,关于LeetCode_前缀树_中等_1268.搜索推荐系统的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 2090. K Radius Subarray Averages【前缀和,滑动窗口,数组】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月11日
    浏览(44)
  • 【leetcode刷题之路】初级算法(2)——链表+树+排序和搜索+动态规划

    3.1 【链表】删除链表中的节点 https://leetcode.cn/problems/delete-node-in-a-linked-list/ 给出的就是要删除的那个节点,直接前后移动就行了。 3.2 【双指针】删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/ 利用双指针left和right,首先让right遍历n个节点,再让两

    2024年02月10日
    浏览(48)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(56)
  • java数据结构与算法刷题-----LeetCode96. 不同的二叉搜索树

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只

    2024年01月21日
    浏览(52)
  • 【LeetCode-中等题】79. 单词搜索

    需要一个标记数组 来标志格子字符是否被使用过了 先找到word 的第一个字符在表格中的位置,再开始递归 递归的结束条件是如果word递归到了最后一个字符了,说明能在矩阵中找到单词 剪枝条件 就是如果已经找到单词了 res = true 了 后面就不需要递归了,还有如果下标越界、

    2024年02月09日
    浏览(37)
  • 【算法刷题day20】Leetcode:654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

    草稿图网站 java的Deque 题目: 654. 最大二叉树 解析: 代码随想录解析 解题思路 NLR的建树 代码 总结 暂无 题目: 617.合并二叉树 解析: 代码随想录解析 解题思路 如果都为root1, root2都为空,返回null;如果root1为空,root2不为空,返回root2;如果roo1不为空,root2为空,返回root

    2024年04月10日
    浏览(38)
  • 【算法刷题day22】Leetcode:235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 50.删除二叉搜索树中的节点

    文档链接:[代码随想录] 题目链接:235. 二叉搜索树的最近公共祖先 题目: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深

    2024年04月13日
    浏览(40)
  • LeetCode_二分搜索_中等_2594.修车的最少时间

    给你一个整数数组 ranks ,表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n 2 分钟内修好 n 辆车。 同时给你一个整数 cars ,表示总共需要修理的汽车数目。请你返回修理所有汽车最少需要多少时间。 注意:所有机械工可以同时修理

    2024年02月09日
    浏览(42)
  • LeetCode 2811. Check if it is Possible to Split Array【脑筋急转弯;前缀和+动态规划或记忆化DFS】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月13日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包