Code & Func

第29天。

今天的题目是Add and Search Word - Data structure design:

一道字典树的题目，如果知道字典树是怎样的话，应该不难做。不过这道题直接套字典树是不行的，因为它需要支持 . 字符来标识任意字符，所以我们在Search的时候需要做一定的修改。简单的来说就是原本用一个指针进行搜索，现在需要一个队列来维护多个指针进行搜索，恩，仅此而已。代码如下：

1
class TrieNode{
2

3
public:
4
    char c;
5
    vector<TrieNode*> childs;
6
    bool flag;
7
    TrieNode(char _c):c(_c),childs(26, nullptr),flag(false) {
8
    }
9
    TrieNode *addChild(char c) {
10
        if (childs[c - 'a']) return childs[c - 'a'];
11
        else return childs[c - 'a'] = new TrieNode(c);
12
    }
13
};
14

15
class WordDictionary {
46 collapsed lines
16
    TrieNode *root;
17
public:
18
    /** Initialize your data structure here. */
19
    WordDictionary():root(new TrieNode('?')) {
20

21
    }
22

23
    /** Adds a word into the data structure. */
24
    void addWord(string word) {
25
        //cout << "Add " << word << endl;
26
        TrieNode *p = root;
27
        for(auto c: word) {
28
            p = p->addChild(c);
29
        }
30
        p->flag = true;
31
    }
32

33
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
34
    bool search(string word) {
35
        // cout << "Search " << word << endl;
36
        queue<TrieNode *> q;
37
        q.push(root);
38
        for(auto c: word) {
39
            if (q.empty()) return false;
40
            // cout << c << " ";
41
            if (c == '.') {
42
                for(int i = 0,size = q.size();i < size; i++) {
43
                    TrieNode *p = q.front(); q.pop();
44
                    for(int j = 0;j < 26;j++) {
45
                        if (p->childs[j]) q.push(p->childs[j]);
46
                    }
47
                }
48
            } else {
49
                for(int i = 0,size = q.size();i < size; i++) {
50
                    TrieNode *p = q.front(); q.pop();
51
                    if (p->childs[c - 'a']) q.push(p->childs[c - 'a']);
52
                }
53
            }
54
        }
55
        while(!q.empty()) {
56
            if (q.front()->flag) return true;
57
            q.pop();
58
        }
59
        return false;
60
    }
61
};