LeetCode刷题【1268】搜索推荐系统

给你一个产品数组 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 中所有字符都是小写英文字母。

字典树基本模板基本应用

字典树基本模板先写出来，然后稍微改下就可以了

1. 对String[] products遍历 构建字典树
2. Node节点上保存对应的字符串，遍历到的时候直接把字符串塞过来，只保留3个，且按照字典序排序，这里借用到TreeSet结构的特性
3. search的时候没遍历到一个节点就把对应Node上的字符串存下来
4. 最终返回

class Solution {
    List<List<String>> res;
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie trie = new Trie();
        for (String product : products) {
            trie.insert(product);
        }
        return trie.search(searchWord);
    }

    class Trie{

        Node root;

        public Trie(){
            root = new Node();
        }

        public void insert(String word){
            int idx = -1;
            Node cur = root;
            while (++idx < word.length()){
                int i = word.charAt(idx) - 'a';
                if (cur.children[i] == null){
                    cur.children[i] = new Node();
                }
                cur = cur.children[i];
                cur.addWord(word);
            }
            cur.flag = true;
        }

        public List<List<String>> search(String word){
            List<List<String>> res = new ArrayList<>();
            int idx = -1;
            Node cur = root;
            while (++idx < word.length()){
                List<String> list = new ArrayList<>();
                int i = word.charAt(idx)-'a';
                if (cur!=null){
                    cur = cur.children[i];
                    list = cur==null?new ArrayList<>():new ArrayList<>(cur.treeSet);
                }
                res.add(list);
            }
            return res;
        }

        class Node{
            boolean flag;
            Node[] children;
            TreeSet<String> treeSet;

            public Node(){
                flag = false;
                children = new Node[26];
                treeSet = new TreeSet<>();
            }

            public void addWord(String word){
                treeSet.add(word);
                if (treeSet.size()>3){
                    treeSet.pollLast();
                }
            }
        }
    }
}