208. Implement Trie (Prefix Tree), 자바 풀이

[문제]
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

class Node {
    public HashMap<Character, Node> children;
    public boolean isEndOfWord;

    public Node() {
        children = new HashMap<>(); // 노드 생성시 자식 노드들에 대해 초기화한다.
        isEndOfWord = false; // 단어의 마지막임을 나타내며 초기화 한다.
    }
}


class Trie {
    private Node root;

    public Trie() {
        this.root = new Node();
    }
    
    public void insert(String word) {
        insert(root, word);
    }   

    public void insert(Node node, String word) {
        if (word.length() == 0) {
            node.isEndOfWord = true;
            return;
        }

        char c = word.charAt(0);
        Node child = node.children.get(c); 

        if (child == null) {
            child = new Node();
            node.children.put(c, child); // 노드의 자식기준으로 문자가 포함되어있지 않다면 자식을 새로 만들어주자
        }

        insert(child, word.substring(1)); // Trie에 저장한 0번째 문자를 제외한 1부터 마지막 인덱스까지의 문자열을 재귀한다.
    }
    
    public boolean search(String word) {
        if (search(root, word, new StringBuilder()) == null) {
            return false;
        } else {
            return true;
        }
    }

    public String search(Node node, String word, StringBuilder sb) {
        if (word.length() == 0) {
            return node.isEndOfWord ? sb.toString() : null;
        }

        char c = word.charAt(0);
        Node nowNode = node.children.get(c);
        
        if (nowNode == null) {
            System.out.println(c);
            return null;
        }

        return search(nowNode, word.substring(1), sb.append(c));
    }
    
    public boolean startsWith(String prefix) {
        Node nowNode = this.root;

        // prefix의 노드들을 연결하는 과정
        for (char c : prefix.toCharArray()) {
            Node childNode = nowNode.children.get(c);

            if (childNode == null) {
                return false;
            }

            nowNode = childNode;
        }

        return startsWith(nowNode, prefix.charAt(prefix.length() - 1));
    }

    public boolean startsWith(Node node, char c) {
        // 만약 탐색 중 단어를 찾았을 경우 return true
        if (node.isEndOfWord == true) {
            return true;
        }
        
        // prefix의 마지막 문자를 기준으로 이어지는 자식들을 찾는다.
        HashMap<Character, Node> map = node.children;
        
        // 자식들의 다음 노드를 계속해서 재귀로 탐색한다.
        for (Character key : map.keySet()) {
            Node nextNode = map.get(key);
            // 단어를 찾았다면 return true
            if (startsWith(nextNode, key)) {
                return true;
            }
        }

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

Trie 자료구조를 이용하여 문자열을 저장, 검색.
접두사를 통한 문자열 탐색을 구현하는 문제이다.

Tree 구조의 그래프를 활용하여 문제를 해결했다.

(0) Node
각각의 노드들은 다음 문자로의 관계를 표현하기위해 HashMap<Character, Node> 형태의 자식과 지금까지의 문자열이 단어 단위로 저장되었는지 확인하기 위한 boolean 타입의 isEndOfWord를 필드로 가지고있다.

(1) Insert
빈 루트 노드를 시작으로 insert 되는 문자열들의 문자들이 순서대로 자식으로 생성되었는지 확인하기 위해 재귀탐색의 과정을 거쳤다.

(2) Search
탐색또한 비슷하게 빈 루트 노드를 기준으로 탐색하려는 문자열들의 문자를 자식으로 포함하고 있는지 여부를 판단 후 StringBuilder에 문자열을 추가해 재귀적으로 탐색하는 과정을 거쳤다. 탐색하려는 문자열을 점점 줄여가기 때문에 길이가 0이 되었을 때, 현재 노드의 isEndOfWord 여부에 따라 문자열을 발견했는지 판단한다.

(3) startsWith
접두사를 포함하는 문자열을 찾기 위한 함수이다. 빈 루트를 기준으로 반복문을 통해 문자열의 마지막 문자의 노드를 찾는다.
해당 노드를 기준으로 추가적으로 재귀 탐색을 하며, 탐색 도중 isEndOfWord 여부를 기준으로 탐색을 종료한다. (접두사를 포함하는 단어가 있다면 탐색 도중 isEndOfWord가 True인 경우를 발견한다.)

재귀적인 탐색 이외에도 반복문을 통해 Trie 구조를 구현할 수 있지만, 가독성이나 유지보수 측면에서 재귀가 더 효율적이라고 생각하여 재귀 탐색으로 구현해보았다.