Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.4 kB
0
Indexable
Never
class Solution {
    class Node {
        Node[] links;
        public PriorityQueue<String> pq;

        public Node() {
            links = new Node[26];
            pq = new PriorityQueue<>((a,b) -> b.compareTo(a));
        }

        private boolean containsKey(char c) {
            return links[c - 'a'] != null;
        }

        private void put(char c, Node node) {
            links[c - 'a'] = node;
        }

        private Node get(char c) {
            return links[c - 'a'];
        }

        private void insertWord(String word) {
            pq.add(word);
        }

        private List<String> getsuggestedWord() {
            List<String> topThree = new ArrayList<>();
            while (!pq.isEmpty() && topThree.size() < 4) topThree.add(pq.poll());
            Collections.reverse(topThree);
            return topThree;
        }
    }

    class Trie {
        Node root;

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

        private void insert(String word) {
            Node node = root;

            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);

                if (!node.containsKey(c)) {
                    node.put(c, new Node());
                }
                
                node = node.get(c);
                node.insertWord(word);
                
            }

        }

        private List<List<String>> getSuggestedProducts(String searchWord) {
            Node node = root;
            List<List<String>> ans = new ArrayList<>();

            for (int i = 0; i < searchWord.length(); i++) {
                char c = searchWord.charAt(i);
                if (node.containsKey(c)) {
                    node = node.get(c);
                    ans.add(node.getsuggestedWord());
                }
                else {
                    ans.add(new ArrayList<String>());
                }
            }
            return ans;
        }

    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie trie = new Trie();
        for (int i = 0; i < products.length; i++) {
            trie.insert(products[i]);
        }

        List<List<String>> results = trie.getSuggestedProducts(searchWord);
        return results;
        

    }
}
Leave a Comment