208. Implement Trie (Prefix Tree)

---

문제 분석

Trie() 클래스를 구현하는 문제

---

풀이 과정

Trie() - 겍체 초기화
insert(String word) - 문자열 추가
search(String word) - 해당 문자열이 Trie에 존재하면 True, 아니면 false
startsWith(String prefix) - 해당 문자열을 접두사로 가진다면 문자열이 있는 경우 true, 아니면 false

Trie는 트리의 일종인 문자열의 키를 효율적으로 저장하고 검색할 수 있는 자료 구조이다.
Node 에 Map<Character, Node> 로 저장을 하고
해당 Character 가 마지막 문자인지 확인하는 boolean isEndOfWord 를 가진다.

• 추가

루트 노드 와 단어를 매개변수로 넘기며 해당 메서드가 시작된다.
오버로딩을 통해 메서드를 정의했고 문자열을 한 글자씩 잘라서 Map 에 추가하게 된다.
이 때 동일한 단어가 없다면 새로운 노드를 만들어 추가한다.
Map 은 키 : Character, 밸류 : Node 가 된다.

• 검색

루트 노드 와 단어를 매개변수로 넘기며 해당 메서드가 시작된다.
오버로딩을 통해 메서드를 정의했고 Map 에 추가한 값을 찾기 시작한다.
만약 문자로 찾았을 때 Node 가 null 이라면 false 를 리턴하고 종료한다.
null 이 아니라면 마지막 문자인지 확인하는 boolean isEndOfWord 를 리턴한다.

• 접두사

루트 노드 와 단어를 매개변수로 넘기며 해당 메서드가 시작된다.
오버로딩을 통해 메서드를 정의했고 Map 에 추가한 값을 찾기 시작한다.
검색과 다른 로직은 단 하나, boolean isEndOfWord 를 리턴하지 않고
한 글자씩 잘라서 매개변수로 넘긴 문자열이 0일 경우 true, 나머진 false 를 리턴한다.

---

나의 생각

시간 복잡도의 성능은 아쉽지만 처음 접하는 자료구조를 받아들이고 이해하는 것에 초점을 맞췄다. 기본적인 구조에서 어떻게 재귀적으로 구현을 할지를 주로 생각하였다.

---

코드

class Trie {

    Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        insert(this.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));
    }
    
    public boolean search(String word) {
        return search(this.root, word);
    }

    public boolean search(Node node, String word) {
        if (word.length() == 0) {
            return node.isEndOfWord;
        }

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

        if (child == null) return false;

        return search(child, word.substring(1));
    }
    
    public boolean startsWith(String prefix) {
        return startsWith(this.root, prefix);
    }

    public boolean startsWith(Node node, String prefix) {
        if (prefix.length() == 0) return true;
        
        char c = prefix.charAt(0);
        Node child = node.children.get(c);

        if (child == null) return false;

        return startsWith(child, prefix.substring(1));
    }

}

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

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