(Tree, Medium) Design Add and Search Words Data Structure

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/

이것도 문제를 보면 기본적으로 Trie를 생각해야 할 것 같다.
마찬가지로 각 노드당 isEnd 플래그를 두어 끝 문자까지 탐색이 완전히 되었는지 본다.

기본 Trie 구현문제와 달리 이 문제에서 생각해야 할 것은 와일드 카드가 있다는 것이다.
. 입력은 어떤 캐릭터와도 매치될 수 있다.

그러므로 search 메서드의 구현은 기본 Trie 구현과는 조금 달라야 한다.

기본 구현에서는 조건이 참인 경우 node 포인터를 계속 바꿔가면서 했다면,
이 문제는 와일드카드인 경우의 체이닝과 기본 문자일 때의 체이닝이 다르기 때문이다.

즉, . 캐릭터가 들어온 순간 해당 깊이의 모든 자식들을 순회 대상에 포함해야 한다.
그러므로 dfs 방식, 메서드 분리하여 재귀로 풀어낸다.

일반 캐릭터라면 기본과 같이 child의 캐릭터로 계속 이어 나가면 되고,
.라면 모든 child에 대해 계속 이어나가면 된다.

class WordDictionary {

    private Node root;
    private static class Node {
        Map<Character, Node> child;
        boolean isEnd;
        public Node() {
            this.child = new HashMap<>();
        }
    }

    public WordDictionary() {
        root = new Node();
    }
    
    public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            node.child.putIfAbsent(c, new Node());
            node = node.child.get(c);
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    private boolean dfs(Node node, String word, int i) {
        if (node == null) {
            return false;
        }
        if (i >= word.length()) {
            return node.isEnd;
        }
        
        char c = word.charAt(i);
        if (c == '.') {
            for (char k : node.child.keySet()) {
                if (dfs(node.child.get(k), word, i + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            if (!node.child.containsKey(c)) {
                return false;
            }
            return dfs(node.child.get(c), word, i + 1);
        }
    }
}