class Solution {
    class TrieNode{
        boolean isWord = false;
        TreeMap <Character, TrieNode>  children = new TreeMap();
    }

    class Trie{
        TrieNode root = new TrieNode();

        public void add(String word){
            TrieNode curr = root;
            for(Character c: word.toCharArray()){
                if (!curr.children.containsKey(c)) curr.children.put(c, new TrieNode());
                curr = curr.children.get(c);
            }
            curr.isWord = true;
        }

        public List<String> getWordsWithPrefix(String prefix){
            ArrayList<String> ans = new ArrayList();
            TrieNode curr = root;
            for(Character c: prefix.toCharArray()){
                if (curr.children.containsKey(c)) {
                    curr = curr.children.get(c);
                } else return ans;
            }
            StringBuilder sb = new StringBuilder(prefix);
            getWords(sb, curr, ans);
            return ans;
        }

        public void getWords(StringBuilder sb,TrieNode curr, ArrayList<String> ans){
            if (curr.isWord) {
                ans.add(sb.toString());
            }
            for(Map.Entry<Character, TrieNode> child:curr.children.entrySet()){
                if (ans.size() <3) {
                    sb.append(child.getKey());
                    getWords(sb, child.getValue(), ans);
                    sb.deleteCharAt(sb.length()-1);
                }
                else break;
            }
        }
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie trie = new Trie();
        for(String product:products){
            trie.add(product);
        }
        List<List<String>> result = new ArrayList();
        StringBuilder sb = new StringBuilder();
        for(char c:searchWord.toCharArray()){
            sb.append(c);
            result.add(trie.getWordsWithPrefix(sb.toString()));
        }
        return result;
    }
}