문제

새 단어를 추가하고 문자열이 이전에 추가된 문자열과 일치하는지 확인할 수 있는 데이터 구조를 설계합니다.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"][],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

구현 전 예상 풀이

오늘 수업시간에 배운 트라이 자료구조를 이용하면 쉽게 풀 수 있을 것 같다.
트라이는 문자열 탐색에 특화된 트리 자료구조이다.

구현 코드

class WordDictionary {
    Node root = new Node();

    public WordDictionary() {
        
    }
    
    public void addWord(String word) {
        addRec(root, word, 0);
    }
    
    public boolean search(String word) {
        return findRec(root, word, 0);
    }

    private void addRec(Node parent, String word, int i){
        if (i == word.length()){
            parent.isEndOfWord = true;
            return;
        }

        char c = word.charAt(i);
        Node child = parent.child(c);
        addRec(child, word, i + 1);
    }

    private boolean findRec(Node parent, String word, int i) {
        if (i == word.length()) {
            return parent.isEndOfWord;
        }

        char c = word.charAt(i);

        if (c == '.') {
            List<Node> children = parent.getChildren();
            for (Node child : children) {
                boolean result = findRec(child, word, i + 1);
                if (result) return true;
            }

            return false;
        }

        Node child = parent.find(c);
        if (child == null) {
            return false;
        }

        return findRec(child, word, i + 1);
    }

    static class Node{
        private final Map<Character, Node> children = new HashMap<>();
        public boolean isEndOfWord;

        public Node child(char c) {
            if (children.containsKey(c)) {
                return children.get(c);
            }

            Node node = new Node();
            children.put(c, node);
            return node;
        }

        public Node find(char c) {
            return children.getOrDefault(c, null);
        }

        public List<Node> getChildren() {
            return new ArrayList<>(children.values());
        }
    }
}

211. Design Add and Search Words Data Structure