力扣---1268. 搜索推荐系统-JZTXT

给你一个产品数组 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 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。

先用前缀树写一遍。

由于只要求前缀，所以不需要 isEnd 。利用一个优先队列维持 3 的长度。

class Solution {
    static class Trie {
        PriorityQueue<String> suggests;
        Trie[] children;

        public Trie () {
            this.suggests = new PriorityQueue<>((a, b) -> {
                return b.compareTo(a);
            });
            this.children = new Trie[26];
        }

        public void insert (String word) {
            Trie trie = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int index = ch - 'a';
                if (trie.children[index] == null) {
                    trie.children[index] = new Trie();
                }
                // 由于需要前缀相同，所以需要存入子优先队列中。
                trie = trie.children[index];
                trie.suggests.add(word);
                // 维持长度为 3 
                if (trie.suggests.size() > 3) {
                    trie.suggests.poll();
                }
            }
        }

        public List<String> getRes (Trie trie) {
            if (trie == null) {
                return new ArrayList<>();
            }
            return new ArrayList<>(trie.suggests);
        }
    }
    public List<List<String>> suggestedProducts (String[] products, String searchWord) {
        Trie trie = new Trie();
        for (String product : products) {
            trie.insert(product);
        }
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < searchWord.length(); i++) {
            char ch = searchWord.charAt(i);
            int index = ch - 'a';
            if (trie != null) {
                trie = trie.children[index];
            }
            if (trie != null) {
                List<String> list = trie.getRes(trie);
                Collections.sort(list);
                res.add(list);
            } else {
                res.add(new ArrayList<>());
            }
        }
        return res;
    }
}