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

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

Design Add and Search Words Data Structure - LeetCode

사전에 단어를 추가하고 검색하는 자료구조를 구현하는 문제다.

addWord 호출시에는 해당 단어를 추가하고,

search 호출시에는 해당 단어가 사전에 있는지 확인한다.

이 때 주의할 점은, . 이 들어간 경우엔 모든 알파벳을 의미하며, 딱 해당 알파벳에서 단어가 끝나야 한다는 것이다.

즉, bat가 있을 때, b 를 검색할 경우 b에서 단어가 끝나지 않으므로 false가 리턴된다.

 

Trie 구조를 사용하는 문제다.

Trie를 만들어주는데, 각각의 Trie 마다 알파벳을 담을 26개의 자식 Trie를 만들어주고, 끝이 될 수 있는지 판단하는 bool type의 isEnd 를 기본값 false로 추가해주자.

 

addWord 호출시에 해당 단어의 모든 알파벳을 훑으며

Trie에 추가해준다.

그리고 마지막 알파벳의 Trie는 isEnd 를 true로 바꿔주자.

 

search 호출시에는 Trie, word, idx를 인자로 받는 재귀메소드를 하나 만들어주자.

그냥 알파벳이 들어올 경우에는 Trie에 해당 알파벳이 있는지 확인해주고, 없다면 false를, 있다면 다음 Trie로 재귀반복한다.

이 때, idx==word.size() 가 되면 해당 Trie의 isEnd를 리턴해주면 된다.

. 이 들어올 경우에는 a부터z까지 다시 넣어 탐색해주자.

 

전체 풀이 코드

class WordDictionary {
public:
    struct Trie{
        bool isEnd = false;
        Trie* child[26];
    };
    Trie* root;
    WordDictionary() {this->root = new Trie();}
    void addWord(string word) {
        Trie* trie = root;
        for (int i=0; i<word.size(); i++) {
            if (!trie->child[word[i]-'a']) trie->child[word[i]-'a'] = new Trie();
            trie = trie->child[word[i]-'a'];
        }
        trie->isEnd=true;
    }
    bool search(string word) {return run(root, word, 0);}
    bool run(Trie* trie, string word, int idx) {
        if (idx==word.size()) return trie->isEnd;
        bool ret = false;
        if (word[idx]=='.') {
            for (int i=0; i<26; i++) ret = ret || (trie->child[i] && run(trie->child[i], word, idx+1));
            return ret;
        } else {
            if (!trie->child[word[idx]-'a']) return false;
            return run(trie->child[word[idx]-'a'], word, idx+1);
        }
    }
};