211. Design Add and Search Words Data Structure

문제 링크: https://leetcode.com/problems/design-add-and-search-words-data-structure/?envType=study-plan-v2&envId=top-interview-150

문제

새 단어 추가 및 이전에 추가한 문자열 탐색 기능을 지원하는 자료 구조를 설계하자.

• WordDictionary(): 생성자

• void addWord(word): 자료구조에 단어 추가

• void search(word): 자료 구조에 단어와 일치하는 문자열이 있다는 true, 아니면 false를 반환한다. 단어는 . 을 포함할 수 있으며, 여기서 . 은 모든 문자와 일치하다고 판단한다.

• 검색어에는 최대 2개의 점 포함 가능

나의 풀이

접근

이전에 봤던 다른 풀이를 참고해 한 번 작성해보려고 했다. 하지만, . 을 포함하고 있는 단어를 탐색하는 것이 복병이었다.

. 을 포함하고 있는 단어를 탐색하는 것은

. 글자가 있다면 . 글자 하위 트리에 있는 모든 글자를 탐색해, true를 반환한다면, 그대로 true를 반환하고,

하위트리를 모두 탐색했는데, true를 반환하지 않는다면 false를 반환하도록 하면 되겠다고 생각했다.

구현 코드

아래의 코드는 테스트 케이스는 통과했지만, 전체 테스트 케이스는 통과하지 못했다.

class WordDictionary {

    Node root;

    public WordDictionary() {
        root = new Node();
    }
    
    public void addWord(String word) {
        root.addWord(word, 0);
    }
    
    public boolean search(String word) {
        return root.search(word, 0);
    }

    class Node {
        boolean isEnd;
        Map<Character, Node> nodes;

        public Node() {
            nodes = new HashMap();
        }

        public boolean search(String word, int idx) {
            if (idx >= word.length()) {
                System.out.println("word.length()");
                return false;
            }
            
            if (idx == word.length() - 1 && isEnd)
                return true;

            char c = word.charAt(idx);
            if (c == '.') {
                for (Map.Entry<Character, Node> node : nodes.entrySet()) {
                    if (node.getValue().search(word, idx + 1))
                        return true;
                    System.out.println(node.getKey());
                }
                return false;
            }
            Node node = nodes.get(c);

            if (node == null) {
                System.out.println("node == null");
                return false;
            }

            return node.search(word, idx + 1);
        }

        public void addWord(String word, int idx) {
            if (idx >= word.length()) {
                isEnd = true;
                return;
            }

            char c = word.charAt(idx);
            Node node = nodes.get(c);
            if (node == null) {
                node = new Node();
                nodes.put(c, node);
                node = nodes.get(c);
            }

            if (idx == word.length() - 1)
                node.isEnd = true;
            
            node.addWord(word, idx + 1);
        }
    }
}

---

다른 풀이

왜 내 코드가 작동을 안 하는지 알기 위해, HashMap을 사용한 다른 풀이를 찾아보았다.

addWord가 작동할 때, isEnd를 적절한 위치에 넣지 않았기 때문에, 내 코드가 작동하지 않았다. 아래의 코드는 다른 풀이인데 사용한 아이디어는 같기 때문에 코드 해석은 생략한다.

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isWord;
    
    public TrieNode() {
        children = new HashMap<>();
        isWord = false;
    }
}

class WordDictionary {
    private TrieNode root;

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

    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.children.containsKey(c)) {
                node.children.put(c, new TrieNode());
            }
            node = node.children.get(c);
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        return searchHelper(root, word, 0);
    }

    private boolean searchHelper(TrieNode node, String word, int index) {
        if (index == word.length()) {
            return node.isWord;
        }
        char c = word.charAt(index);
        if (c == '.') {
            for (TrieNode child : node.children.values()) {
                if (searchHelper(child, word, index + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            TrieNode child = node.children.get(c);
            if (child == null) {
                return false;
            }
            return searchHelper(child, word, index + 1);
        }
    }
}