[Java] 211. Design Add and Search Words Data Structure

문제 파악

특정 문자열을 보관하고 search 했을 때, 존재하면 true를 반환하는 자료구조를 만들어야한다.

 

. 이 포함된 경우는 어떠한 문자가 들어가도 허용된다.

---

풀이

1️⃣ Trie 자료구조를 이용한 풀이

💡 떠오른 Idea

Trie 자료구조를 이용하면 접두어나 부분 문자열을 검색할 수 있다.

따라서, Trie 자료구조를 구현하였다.

특히, 이 문제에서는 search 과정에서 . 이 포함되어 있는 경우는

해당 노드가 갖는 모든 자식 노드들을 탐색하도록 구현하여 해결할 수 있을 것이라 판단하였다.

 

import java.util.*;

class WordDictionary {

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

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

        }
    }

    Node root;

    public WordDictionary() {
        root = new Node();
    }

    public void addWord(String word) {
        addWord(this.root, word);
    }

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

        char ch = word.charAt(0);
        Node child;
        if (node.children.containsKey(ch)) {
            child = node.children.get(ch);
        } else {
            child = new Node();
            node.children.put(ch, child);
        }

        addWord(child, word.substring(1));
    }

    public boolean search(String word) {
        return search(this.root, word);
    }

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

        char ch = word.charAt(0);
        if (ch == '.') {

            for (Node child : node.children.values()) {
                if (search(child, word.substring(1))) {
                    return true;
                }
            }
            return false;
        }

        if (!node.children.containsKey(ch)) {
            return false;
        } else {
            return search(node.children.get(ch), word.substring(1));
        }

    }
}

 

결과

---

📖 회고

Trie 자료구조의 가장 큰 특징 중의 하나인 부분 문자열 검색을 직접 구현해볼 수 있는 문제였다.

 

다른 코드를 참고하지 않고 직접 구현하면서, 동작 메커니즘을 이해할 수 있었다.