[leetcode] 208. Implement Trie(Prefix Tree)

Trie

트라이라고 하는 자료구조가 존재하는데 문자열을 저장하고 탐색하기 위해 사용된다고 한다. 특히 단어 검색 알고리즘에 사용된다고 한다.

문자열 저장을 위한 메모리를 어느정도 차지하고는 있지만 O(n)으로 굉장히 빠르다.

 

이 링크를 보고..공부하며 아래 코드 구현하였다. (설명 완벽..)

 

Node는 문자 Character 키와 연결되는 Node를 가지는 HashMap과 해당 노드가 문자열의 마지막 문자인지를 알려주는 endOfWord로 이루어져 있다.

 

하나의 노드가 다양한 노드로 뻗어나가기 위해 HashMap을 사용한 것 같다.

class Trie {
    public Node root;
    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node node = root;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            node.child.putIfAbsent(c,new Node());
            node = node.child.get(c);
        }
        node.endOfWord = true;
    }
    
    public boolean search(String word) {
        Node node = root;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.child.containsKey(c)) {
                node = node.child.get(c);
            } else {
                return false;
            }
        }
        return node.endOfWord;
    }
    
    public boolean startsWith(String prefix) {
        Node node = root;
        for(int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (node.child.containsKey(c)) {
                node = node.child.get(c);
            } else {
                return false;
            }
        }
        return true;
    }

    class Node {
        public HashMap<Character, Node> child;
        public boolean endOfWord;

        public Node() {
            child = new HashMap<>();
            endOfWord = false;
        }
    }
}

/**
 * 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);
 */