1268. Search Suggestions System

T: O(M), M is the total number of chars in products for buiding Trie

S: O(26n + m), n is the number of trie nodes, m is the output for len of searchWord

class Solution {
    class TrieNode {
        private Map<Character, TrieNode> sons;
        private boolean isWord;
        private String word;
        TrieNode() {
            sons = new HashMap<>();
            word = "";
        }
    }
    
    private TrieNode root;
    Solution() {
        root = new TrieNode();
    }
    
    private void buidTrie(String[] products) {
        
        for (String product : products) {
            TrieNode node = root; // dont forget node move to root, then start
            for (char c : product.toCharArray()) {
                node.sons.putIfAbsent(c, new TrieNode());
                node = node.sons.get(c);
            }
            node.isWord = true;
            node.word = product;
        }
    }
    private List<String> startWith(String word) {
        List<String> result = new ArrayList<>();
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            TrieNode next = node.sons.get(c);
            if (next == null) {
                return result;
            }
            node = next;
        }
        
        dfs(node, result, word);
        
        return result;
    }
    
    private void dfs(TrieNode node, List<String> list, String prefixWord) {
        if (list.size() == 3) {
            return;
        }
        if (node.isWord) {
            list.add(node.word);
        }
        
        // why need a~z, because base on prefix, we want to find the entire string, 
        // so with prefix + next possible char, keep using dfs to find the ans (node.isWord == true)
        for (char c = 'a'; c <= 'z'; c++) {
            StringBuilder newPrefix = new StringBuilder();
            newPrefix.append(c);
            if (node.sons.get(c) != null) {
                dfs(node.sons.get(c), list, newPrefix.toString());
            }
        }
    }

    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> result = new ArrayList<>();
            
        buidTrie(products);
        StringBuilder sb = new StringBuilder();
        // but this Q needs entire String, so use DFS
        for (char c : searchWord.toCharArray()) { // here is part String (after each keyin new char)
            sb.append(c);
            List<String> list = startWith(sb.toString());
            result.add(list);
        }
        return result;
    }

}

/*
at most

have common prefix with searchWord

after each character of searchWord is typed
so each character is typed return at most 3 products

only 3

*/