[007]Add and Search Word - Data structure design

 

문제: https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3413/

---

문자열 검색 문제. 와일드 카드 식별자가 존재해도 문자열 & 검색문제이므로 트라이로 해결이 가능합니다.

 

class WordDictionary {
public:
    
    static const int ALPHA_SIZE = 128;
    
    typedef struct Trie {
        
        Trie* next[ALPHA_SIZE];
        bool isFinished;
        
        Trie() {
            fill(next, next + ALPHA_SIZE, nullptr);
            isFinished = false;
        }
        
        void insert(const char *key) {
            if (*key == '\0') {
                isFinished = true;
                return;
            }   
            else {
                if (next[*key] == nullptr) {
                    next[*key] = new Trie();
                }
                
                next[*key]->insert(key+1);
            }
        }
        
        bool find(const char *key) {
            if (*key == '\0') {
                return isFinished == true ? true : false;
            }
            else if (*key == '.') {
                bool result = false;
                for (int loop = 0; loop < ALPHA_SIZE; ++loop) {
                    if (next[loop]) {
                        if (next[loop]->find(key+1)) {
                            result = true;
                        }
                    }
                }
                return result;
            }
            else {
                if (next[*key] == nullptr)
                    return false;
                else {
                    return next[*key]->find(key+1);
                }
            }
        }
    }Trie;

    Trie* root;
    
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new Trie();
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        root->insert(word.c_str());
    }
    
    /** 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) {
       return root->find(word.c_str());
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */