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

😎풀이

1. TrieNode 클래스를 생성해 문자열의 끝과 자식 문자열을 나타낼 수 있도록 정의한다.
2. addWord 메서드가 호출될 경우, root의 children에 각 문자를 정의하며 종료되는 시점의 TrieNode에 isEnd를 true로 설정한다.
3. search 메서드가 호출될 경우, 깊이 우선 탐색을 진행한다.
   3-1. .은 모든 문자와 비교가 가능하므로 현재 TrieNode의 자식 요소를 모두 한번씩 탐색한다.
   3-2. 현재 TrieNode와 현재 문자를 비교하여 같은 문자가 있을 경우 탐색한다.
4. 모든 비교가 완료되었을 때 해당 문자열이 종료 문자열인지의 여부를 TrieNode의 isEnd를 통해 확인한다.
5. dfs의 결과를 search 메서드의 반환값으로 반환한다.

class TrieNode {
    children: Map<string, TrieNode>;
    isEnd: boolean;
    
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}

class WordDictionary {
    private root: TrieNode;
    
    constructor() {
        this.root = new TrieNode();
    }
    
    addWord(word: string): void {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char)!;
        }
        node.isEnd = true;
    }
    
    search(word: string): boolean {
        return this.dfs(word, 0, this.root);
    }
    
    private dfs(word: string, index: number, node: TrieNode): boolean {
        if (index === word.length) return node.isEnd;
        
        const char = word[index];
        // '.'은 모든 문자와 비교 가능
        if (char === '.') {
            for (const child of node.children.values()) {
                if (this.dfs(word, index + 1, child)) return true;
            }
            return false;
        } else {
            if (!node.children.has(char)) return false;
            return this.dfs(word, index + 1, node.children.get(char)!);
        }
    }
}