[WXM] LeetCode 211. Add and Search Word - Data structure design C++

211. 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.
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.

Approach

제목은 사전 트리를 검색하고 삽입하는 방법을 뜻한다.그리고 정상적인 검색과 조금 다르다. .는 임의의 문자와 일치할 수 있다. 그러면 검색은 DFS를 사용해야 한다. DFS를 어떻게 디자인하는가가 매우 관건적이다. 디자인이 좋지 않아서 이해하기 어려울 뿐만 아니라 복잡해질 수 있기 때문이다. 우선 우리는 문자마다 심도 있게 검색하고 문자를 두 가지 상황으로 나누어야 한다. 하나는 시비., 하나는 .이다. 나는 첫 번째 상황을 먼저 토론한다. 시비. 때문에그래서 문자는 확정된 것이다. 나는 계속 아래로 검색하면 된다. 두 번째 상황은 .이기 때문에 문자는 확실하지 않다. 우리는 26가지 가능성을 열거해서 하나가 될 때까지 해야 한다.귀속 경계는 마지막 문자가 분명하다. 우리는 이 문자가 어떤 단어의 끝인지 판단하기만 하면 된다. 세부 등 부분은 코드를 보는 것이 좋다.

Code

struct Trie
{
    Trie* letter[26];
    bool isword;
    Trie() {
        isword = false;
        for (int i = 0; i < 26; i++) {
            letter[i] = nullptr;
        }
    }
};
class WordDictionary {
public:
    Trie *root;
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new Trie();
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        Trie *head = root;
        for (char &w : word) {
            int c = w - 'a';
            if (!head->letter[c]) {
                head->letter[c] = new Trie();
            }
            head = head->letter[c];
        }
        head->isword = true;
    }
    bool Search_str(string &word, Trie *head, int n, int pos) {
        if (pos == n) {
            if (word[pos] == '.') {
                for (int i = 0; i < 26; i++) {
                    if (!head->letter[i])continue;
                    if (head->letter[i]->isword)return true;
                }
                return false;
            }
            return head&&head->letter[word[pos] - 'a'] && head->letter[word[pos] - 'a']->isword;
        }
        if (word[pos] != '.') {
            if (!head->letter[word[pos] - 'a'])return false;
            return Search_str(word, head->letter[word[pos] - 'a'], n, pos + 1);
        }
        for (int i = 0; i < 26; i++) {
            if (!head->letter[i])continue;
            if (Search_str(word, head->letter[i], n, pos + 1)) {
                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) {
        return Search_str(word, root, word.size() - 1, 0);
    }
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* bool param_2 = obj.search(word);
*/