[PS] Leet | 211. 단어 데이터 추가 및 탐색

문제

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

예시

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

조건

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters.
• word in search consist of '.' or lowercase English letters.
• There will be at most 2 dots in word for search queries.
• At most 104 calls will be made to addWord and search.

답

문자 하나를 하나의 node에 저장하는 Trie 자료구조를 사용합니다.

 

와일드 카드인 '.'가 등장하면 word 내의 모든 자식 node들에 대해 탐색 search()를 호출하고,

 

일반적인 경우라면 wod에서 다음 문자에 해당하는 node를 찾아 탐색 search()를 호출합니다.

 

WordDictionary 자료 구조

var WordDictionary = function() {
    this.data = false;
    this.word = {};
};

addWord( )

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    let i = 0;
    let node = this.word;

    const search = () => {
        if (i === word.length) {
            node["is"] = true;
            return null
        }
        if (!(word[i] in node)) node[word[i]] = {};
        node = node[word[i++]];
        
        return search();
    }
    return search()
};

search( )

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
    const search = (node, i) => {
        if (i === word.length) {
            return node["is"] ?? false
        }
        if (word[i] === '.'){
            for (const suc in node){
                if (suc === "is") continue;
                if (search(node[suc], i+1)) return true
            }
        }
        else if (word[i] in node){
            return search(node[word[i]], i+1);
        }
        return false
    }
    return search(this.word, 0)
};