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

￡神魔★判官ぃ 2023-10-13 17:47 108阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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）前缀树  
思路参考[本题官方题解][Link 1]。

## 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/search-suggestions-system/solutions/101822/suo-tui-jian-xi-tong-by-leetcode-solution/?envType=study-plan-v2&envId=leetcode-75