211. Design Add and Search Words Data Structure

---

문제 분석

새로운 단어를 추가하고 문자열이 이전에 추가된 문자열과 일치하는지 찾는 것을 지원하는 데이터 구조를 설계합니다. (trie)

---

풀이 과정

이전 Trie 자료 구조 구현과 비슷한 문제다.

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

• 추가 기능도 비슷한 로직이다.

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

• 검색

루트 노드 와 단어를 매개변수로 넘기며 해당 메서드가 시작된다.
오버로딩을 통해 메서드를 정의했고 Map 에 추가한 값을 찾기 시작한다.
만약 문자로 찾았을 때 Node 가 null 이라면 false 를 리턴하고 종료한다.
문자열의 길이가 0이라면 boolean isEndOfWord 를 리턴한다.
만약 charAt() 한 문자가 '.' 이라면 values() 메서드를 이용해 노드들을 다 꺼낸 후 탐색을 시작한다.

---

나의 생각

시간 복잡도의 성능은 아쉽지만 처음 접하는 자료구조를 받아들이고 이해하는 것에 초점을 맞췄다. 기본적인 상황 이외에 특정한 상황에서 재귀적인 탐색으로 구현하는 방법에 대해 고민하였다.

---

코드

class WordDictionary {
    
    Node root;

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

    public void addWord(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);
        }

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

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

        char c = word.charAt(0);
        
        if (c == '.') {
            for (Node n : node.children.values()) {
                boolean result = search(n, word.substring(1));
                if (result) return result;
            }
        }

        Node child = node.children.get(c);

        return search(child, word.substring(1));
    }
}

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

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