一个好用的字典树模板(C++)

发表于 分类于 ，

因为大多数题目的字符串都是小写字母，所以就按照这个设计了，共26个英文字母，每个节点占用26个char。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class TrieNode {
public:
    array<TrieNode *, 26> node;
    TrieNode() : node({nullptr}) {}
    void insert(string &s) {
        TrieNode *ptr = this;
        for (auto c: s) {
            c -= 'a';
            if (ptr->node[c] == nullptr) {
                ptr->node[c] = new TrieNode;
            }
            ptr = ptr->node[c];
        }
    }
    bool find(string &s) {
        TrieNode* ptr = this;
        for (auto c: s) {
            c -= 'a';
            if (ptr->node[c] == nullptr) {
                return false;
            } else {
                ptr = ptr->node[c];
            }
        }
        return true;
    }
};