[leetcode] 211. Add and Search Word - Data structure 디자인 문제 해결 보고서

제목 링크:https://leetcode.com/problems/add-and-search-word-data-structure-design/
Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters  a-z  or  . . A  .  means it can represent any one letter.
For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note: You may assume that all words are consist of lowercase letters  a-z .
사고방식: 사전 트리를 실현하고 추가와 찾기 작업을 완성합니다.
그 원리는 각 결점마다 26명의 아이 결점이 있고, 한 결점의 26명의 아이 결점은 처음에는 NULL로 기본값으로 되어 있다.만약에 우리가 단어를 추가하려고 한다면 이 단어는 뿌리 노드에서 아래로 층층이 성장할 것이다. 단어가 끝날 때 우리는 마지막 결점에 표시를 한다. 이것은 뿌리 노드에서 이 결점까지의 경로가 하나의 단어라는 것을 의미한다.
단어를 추가할 때 공통 접두사 단어가 경로를 공유하기 때문에 사전 트리는 메모리를 크게 절약할 수 있습니다.
코드는 다음과 같습니다.

class WordDictionary {
public:
    typedef struct Trie
    {
        vector<Trie*> child;
        bool isWord;
        Trie(): child(vector<Trie*>(26, NULL)), isWord(false){}
    }Trie;
    
    
    WordDictionary():root(new Trie()){}
    
    // Adds a word into the data structure.
    void addWord(string word) {
        Trie* tem = root;
        for(auto ch: word)
        {
            if(tem->child[ch - 'a'] == NULL)// ch ,   
                tem->child[ch - 'a'] = new Trie();
            tem = tem->child[ch - 'a'];
        }
        tem->isWord = true;// 
    }

    bool DFS(string str, Trie* node)
    {
        if(node == NULL) return false;
        if(str.size() ==0) return node->isWord;// , 
        if(str[0] != '.')// . 
        {
            if(node->child[str[0]-'a'] == NULL) return false;
            return DFS(str.substr(1), node->child[str[0]-'a']);
        }
        for(int i = 0; i < 26; i++)// ., 
            if(DFS(str.substr(1), node->child[i]) == true)
                return true;
        return false;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        Trie* tem = root;
        return DFS(word, tem);
    }
    
private:
    Trie* root;
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

참조:https://leetcode.com/discuss/45435/c-using-trie-and-dfs-for-search-easy-understand-solution