[3주차] 208. Implement Trie (Prefix Tree)

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

Implement Trie (Prefix Tree) - LeetCode

---

📝 문제

다음 기능을 가진 Trie 자료구조를 구현하여라.

• Trie(): 객체 초기화
• void insert(String word): Trie에 word 문자열 삽입
• boolean search(String word): 현재 Trie 에 word 문자열이 존재한다면 (이전에 삽입되었다면) true, 그렇지 않으면 false
• boolean startWith(String prefix): 현재 Trie 에 존재하는 단어 중, prefix 문자열을 접두사로 가지는 단어가 존재하면 true, 그렇지 않으면 false

 

🎈 풀이

class Trie {

    private Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node currentNode = root; // root 부터 탐색 시작
        for (int i=0; i<word.length(); i++) {
            char c = word.charAt(i); // 단어의 첫 글자부터 순회
            if (!currentNode.children.containsKey(c)) { // 현재 노드의 자식에 순회하는 현재 문자가 없으면
                currentNode.children.put(c, new Node()); // 현재 노드의 자식에 새 노드 추가
            }

            currentNode = currentNode.children.get(c); 현재 노드를 다음 자식 노드로 교체
        }

        currentNode.endOfWord = true; // 단어의 끝 이므로 true
    }
    
    public boolean search(String word) {
        Node node = getNode(word);
        if (node == null) return false;
        return node.endOfWord == true;
    }
    
    public boolean startsWith(String prefix) {
        return getNode(prefix) != null;
    }

	// endOfWord 와 관계없이 현재 Trie 에 word 가 존재하면 해당 노드 반환, 그렇지 않으면 null
    private Node getNode(String word) {
        Node currentNode = root;
        for (int i=0; i<word.length(); i++) {
            char c = word.charAt(i);
            if (!currentNode.children.containsKey(c)) {
                return null;
            }

            currentNode = currentNode.children.get(c);
        }

        return currentNode;
    }

    private class Node {
        Map<Character, Node> children;
        boolean endOfWord; // 단어의 마지막임을 알리는 플래그

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

 

📈 타 솔루션 참고

private class Node {
    Node[] children
    boolean endOfWord;

    Node() {
        children = new children[26];
        endOfWord = false;
    }
}

기본 로직은 동일하나 HashMap 대신 배열을 사용한 방법이다. 아주 근소한 차이지만 해당 방법이 속도가 더 빨랐다.

HashMap과 달리 초기화할 때 부터 알파벳 26개 전부 공간을 미리 할당해놓고, 새로운 자식이 추가되면 children 의 특정 인덱스에 Node를 생성한다.

 

자식 검색은 인덱싱을 사용한다. 'c' 가 자식에 존재하는지 확인하려면 children['c' - 'a'] 에 접근하여 null 인지 확인한다.