[Trie, Medium] Search Suggestions System

https://leetcode.com/problems/search-suggestions-system/description/?envType=study-plan-v2&envId=leetcode-75

Trie 자료구조를 만들어서 풀어본다.
다만 문제 특성 상 완전히 일치하는 문자 여부 체크는 필요 없고, 대신 해당 문자로 시작하는 추천 상품명들을 담아둘 필요가 있다.

따라서 Node는 다음과 같다.

class Node {
    Map<Character, Node> child = new HashMap<>();
    List<String> suggest = new ArrayList<>();
}

사전 순 정렬이 필요하다고 했으므로 애초에 products를 정렬해 준다.
Arrays.sort(products);

다음으로 Trie인데,
insert 시점에 suggest 사이즈가 3보다 작으면 현재 Trie에 넣으려는 상품명을 suggest에 등록해준다.

getSuggest은 입력받은 키워드를 한 캐릭터씩 순회하면서
Node에서 찾은 suggest를 계속 add해준다.

해당 캐릭터로 찾는 노드가 없으면 빈 ArrayList를 add한다.

    class Trie {
        Node root = new Node();

        public void insert(String product) {
            Node node = root;
            for (char c : product.toCharArray()) {
                node.child.putIfAbsent(c, new Node());
                node = node.child.get(c);

                if (node.suggest.size() < 3) {
                    node.suggest.add(product);
                }
            }
        }

        public List<List<String>> getSuggest(String searchWord) {
            List<List<String>> result = new ArrayList<>();
            Node node = root;

            for (char c : searchWord.toCharArray()) {
                if (node != null && node.child.containsKey(c)) {
                    node = node.child.get(c);
                    result.add(node.suggest);
                } else {
                    node = null;
                    result.add(new ArrayList<>());
                }
            }
            return result;
        }
    }

전체 코드

class Solution {
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        Trie trie = new Trie();

        for (String product : products) {
            trie.insert(product);
        }
        
        return trie.getSuggest(searchWord);
    }

    class Node {
        Map<Character, Node> child = new HashMap<>();
        List<String> suggest = new ArrayList<>();
    }

    class Trie {
        Node root = new Node();

        public void insert(String product) {
            Node node = root;
            for (char c : product.toCharArray()) {
                node.child.putIfAbsent(c, new Node());
                node = node.child.get(c);

                if (node.suggest.size() < 3) {
                    node.suggest.add(product);
                }
            }
        }

        public List<List<String>> getSuggest(String searchWord) {
            List<List<String>> result = new ArrayList<>();
            Node node = root;

            for (char c : searchWord.toCharArray()) {
                if (node != null && node.child.containsKey(c)) {
                    node = node.child.get(c);
                    result.add(node.suggest);
                } else {
                    node = null;
                    result.add(new ArrayList<>());
                }
            }
            return result;
        }
    }
}