LeetCode 208 - Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

Trie 자료구조를 구현하는 문제이다.

우선은 Trie에 대해서 알아보고 코드로 구현해 보자.

Trie는 검색 트리의 줄임말로 때로는 접두사 트리라고도 부른다.

기본적으로 문자열을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조이다.

각 노드가 문자열을 나타내며 루트에서 특정 노드까지 경로가 하나의 문자열을 형성하는 것이다.

이렇게 하면 얻게 되는 장점이 뭘까?

우선 동일한 접두사를 공유할 수 있다는 점이다.

같은 접두사를 가진 문자열들은 같은 노드들을 공유하고 이는 메모리 사용을 효율적으로 만든다.

다음으로는 검색속도이다.

문자열의 존재 여부를 확인하는 데 O(M)의 시간이 걸린다. (M은 문자열의 길이)

무엇보다 접두사 검색에 최적화 돼 있다.

특정 접두사로 시작하는 모든 문자열을 쉽게 찾을 수 있다.

class Trie {

    static class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
        }

        public Map<Character, TrieNode> getChildren() {
            return children;
        }

        public boolean isEndOfWord() {
            return isEndOfWord;
        }

        public void setEndOfWord(boolean endOfWord)  {
            isEndOfWord = endOfWord;
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();    
    }
    
    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current = current.getChildren().computeIfAbsent(ch, x -> new TrieNode());
        }
        current.setEndOfWord(true);
    }
    
    public boolean search(String word) {
        TrieNode node = searchNode(word);
        return node != null && node.isEndOfWord();
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = searchNode(prefix);
        return node != null;
    }

    private TrieNode searchNode(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            TrieNode node = current.getChildren().get(ch);
            if (node == null) return null;
            current = node;
        }
        return current;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */