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

1. 문제

• 요구 사항에 맞는 WordDictionary class를 구현하라.

2. 해결

class TrieNode {
    children: Map<string, TrieNode>;
    isEnd: boolean
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}
class WordDictionary {
    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 {
        const DFS = (node: TrieNode, i:number) => {
            if(i === word.length) return node.isEnd;
           
            const char = word[i];
           
            if(char ==='.') {
                for(const child of node.children.values()) {
                    if(DFS(child, i + 1)) return true;
                }    
                return false;
            } else {
                if(!node.children.has(char)) return false;
                return DFS(node.children.get(char), i + 1)
            }
        }
       
        return DFS(this.root,0)
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

• Trie로 문자열을 구성하고, 처리하면 된다.
• search 쪽에서 . 에 대한 처리가 막혔다.
• 존재하는 모든 자식에 대해 동일한 로직 처리를 해줘야 하므로 재귀 함수로 구현.