Leetcode75 1268搜索推荐系统

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 中所有字符都是小写英文字母。

Solution 1

import java.util.*;

class Trie {

    Map<Character, Trie> map;

    public Trie() {
        map = new HashMap<>();
    }

    public void insert(String word) {
        if (word.length() == 0) {
            map.put(null, null);
        } else {
            char c = word.charAt(0);
            Trie t = map.getOrDefault(c, new Trie());
            map.put(c, t);
            t.insert(word.substring(1));
        }
    }

    public boolean search(String word) {
        if (word.length() == 0) {
            if (map.containsKey(null)) {
                return true;
            } else {
                return false;
            }
        } else {
            char c = word.charAt(0);
            Trie t = map.getOrDefault(c, null);
            if (t == null) {
                return false;
            } else {
                return t.search(word.substring(1));
            }
        }
    }

    public boolean startsWith(String prefix) {
        if (prefix.length() == 0) {
            return true;
        } else {
            char c = prefix.charAt(0);
            Trie t = map.getOrDefault(c, null);
            if (t == null) {
                return false;
            } else {
                return t.startsWith(prefix.substring(1));
            }
        }
    }

    public Trie getTrie(String prefix) {
        if (prefix.length() == 0) {
            return this;
        } else {
            char c = prefix.charAt(0);
            Trie t = map.getOrDefault(c, null);
            if (t == null) {
                return new Trie();
            } else {
                return t.getTrie(prefix.substring(1));
            }
        }
    }

    public List<String> getSuggestions(int count) {
        if (count <= 0) {
            return new ArrayList<>();
        }
        List<String> result = new ArrayList<>(count);
        Character[] keyList = map.keySet().toArray(new Character[0]);
        Arrays.sort(keyList, Comparator.nullsFirst(Comparator.naturalOrder()));
        for (Character c : keyList) {
            if (result.size() == count) {
                break;
            }
            if (c == null) {
                result.add("");
                continue;
            }
            Trie t = map.get(c);
            List<String> subSuggestions = t.getSuggestions(count - result.size());
            for (String subSuggestion : subSuggestions) {
                result.add(c + subSuggestion);
            }
        }
        return result;
    }
}

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> result = new ArrayList<>(searchWord.length());
        Trie trie = new Trie();
        for (String product : products) {
            trie.insert(product);
        }
        for (int i = 1; i <= searchWord.length(); i++) {
            String prefix = searchWord.substring(0, i);
            Trie t = trie.getTrie(prefix);
            List<String> suggestions = t.getSuggestions(3);
            for (int j = 0; j < suggestions.size(); j++) {
                suggestions.set(j, prefix + suggestions.get(j));
            }
            result.add(suggestions);
        }
        return result;
    }
}