前言

博主介紹：?目前全網(wǎng)粉絲2W+，csdn博客專家、Java領(lǐng)域優(yōu)質(zhì)創(chuàng)作者，博客之星、阿里云平臺優(yōu)質(zhì)作者、專注于Java后端技術(shù)領(lǐng)域。

涵蓋技術(shù)內(nèi)容：Java后端、算法、分布式微服務、中間件、前端、運維、ROS等。

博主所有博客文件目錄索引：博客目錄索引(持續(xù)更新)

視頻平臺：b站-Coder長路

---

LeetCode、1268. 搜索推薦系統(tǒng)【中等，前綴樹+優(yōu)先隊列、排序+前綴匹配】

題目類型及分類

題目鏈接：LeetCode、1268. 搜索推薦系統(tǒng)

分類：02數(shù)據(jù)結(jié)構(gòu)/樹/字典樹(前綴樹)

---

思路

API調(diào)用（排序+前綴匹配）

復雜度分析：時間復雜度O(n.logn)；空間復雜度O(n)

class Solution {//prodcuts數(shù)量2萬  單詞1000public List<List<String>> suggestedProducts(String[] products, String searchWord) {//根據(jù)字典序排序Arrays.sort(products);//初始化結(jié)果集合List<List<String>> ans = new ArrayList<>();//遍歷所有的搜索文字for (int i = 0; i < searchWord.length(); i ++) {String s = searchWord.substring(0, i + 1);//結(jié)果集合List<String> res = new ArrayList<>();//遍歷所有productsfor (String product: products) {if (product.startsWith(s)) {res.add(product);}//若是已經(jīng)收集到3個if (res.size() == 3) {break;}}ans.add(res);}return ans;}
}

---

前綴樹+優(yōu)先隊列

使用大頂堆目的：每個單詞只留下3個最小字典序的，因為一旦大頂堆中有>目標數(shù)量時，就會將最大的排除出去。

復雜度分析：時間復雜度O(n)；空間復雜度O(n)

class Solution {//每一個大頂堆中的數(shù)量為3private static final int size = 3;//根節(jié)點private TrieNode root = new TrieNode();//自定義Node節(jié)點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));}}//插入一個產(chǎn)品名稱到前綴樹public void insert(String product) {//拿到當前的前綴樹節(jié)點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];//當前節(jié)點要將單詞添加進來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);}//搜索所有的匹配結(jié)果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];//節(jié)點不為空情況while (node != null && !node.queue.isEmpty()) {tmp.add(node.queue.poll());}//將整個集合翻轉(zhuǎn)Collections.reverse(tmp);//添加到最終的結(jié)果集合中ans.add(tmp);}return ans;}}

---

資料獲取

大家點贊、收藏、關(guān)注、評論啦~

精彩專欄推薦訂閱：在下方專欄👇🏻

• 長路-文章目錄匯總（算法、后端Java、前端、運維技術(shù)導航）：博主所有博客導航索引匯總
• 開源項目Studio-Vue—校園工作室管理系統(tǒng)(含前后臺，SpringBoot+Vue)：博主個人獨立項目，包含詳細部署上線視頻，已開源
• 學習與生活-專欄：可以了解博主的學習歷程
• 算法專欄：算法收錄

更多博客與資料可查看👇🏻獲取聯(lián)系方式👇🏻，🍅文末獲取開發(fā)資源及更多資源博客獲取🍅

---

整理者：長路 時間：2024.2.13