[Trie, Medium] Implement Trie (Prefix Tree)

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

Trie 자료구조를 표현할 클래스가 별도로 필요하다. Node라는 이름의 노드를 만든다.
노드는 child, 그리고 문장의 끝을 의미하는 boolean 변수를 가진다.

child는 배열로 해도 되고 (영문 소문자만 오기 때문에 26자리 배열), 아니면 맵으로 해도 되고..

Trie 클래스의 생성자에서 root는 new Node()로 초기화 해주고,
이제 insert, search, startsWith를 구현해주면 된다.

탐색 시에는 항상 root부터 시작해야 한다.

• insert: 루트부터 시작해서 child에 해당 캐릭터가 없으면 새로 넣고 다음 포인터로.
  순회가 끝났으면 마지막으로 바라보는 포인터의 boolean 변수를 true로.
• search: 루트부터 시작해서 child에 해당 캐릭터가 없으면 바로 false 리턴
  해당 캐릭터가 있으면 포인터 이동
  최종적으로 완전히 같은 문자인지 확인하기 위해 마지막 포인터의 boolean 변수 값 리턴
• startsWith: search와 동일하지만 유일하게 다른 점은 마지막 포인터의 boolean 변수를 볼 필요가 없다는 점. prefix에 대한 캐릭터를 모두 순회하는 동안 child에서 맞는 키를 계속 찾았으면 startsWith는 true다.

class Trie {

    Node root;

    class Node {
        Map<Character, Node> child;
        boolean isEndOfWord;

        public Node() {
            this.child = new HashMap<>();
            this.isEndOfWord = false;
        }
    }

    public Trie() {
        this.root = new Node();
    }
    
    public void insert(String word) {
        Node node = this.root;
        for (char c : word.toCharArray()) {
            node.child.putIfAbsent(c, new Node());
            node = node.child.get(c);
        }
        node.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        Node node = this.root;
        for (char c : word.toCharArray()) {
            if (!node.child.containsKey(c)) {
                return false;
            }
            node = node.child.get(c);
        }
        return node.isEndOfWord;
    }
    
    public boolean startsWith(String prefix) {
        Node node = this.root;
        for (char c : prefix.toCharArray()) {
            if (!node.child.containsKey(c)) {
                return false;
            }
            node = node.child.get(c);
        }
        return true;
    }
}