前缀树是一种数据结构，常用来字符搜索。
2. 实现包含的操作主要是:
加入串搜索串
代码实现，直接用leetcode_208的题解咯。
代码 class Trie { public: Trie():isEnd(false){ for ( int i = 0; i < 26;++i) child[i] = nullptr; } ~Trie() { for ( int i = 0; i < 26; ++i ) { if (child[i]) { delete child[i]; child[i] = nullptr; } } } void insert(string word) { Trie *cur = this; int sz = word.size(); for (int i = 0; i < sz; ++i) { int idx = word[i] - 'a'; if ( cur->child[idx] == nullptr) { Trie *nxt = new Trie(); cur->child[idx] = nxt; } cur = cur->child[idx]; } cur->isEnd = true; } bool search(string word) { Trie *cur = this; int sz = word.size(); for (int i = 0; i < sz; ++i) { int idx = word[i] - 'a'; if (cur->child[idx] == nullptr) return false; cur = cur->child[idx]; } return cur->isEnd; } bool startsWith(string prefix) { int sz = prefix.size(); Trie *cur = this; for (int i = 0; i < sz; ++i ) { int idx = prefix[i] - 'a'; if (cur->child[idx] == nullptr) return false; cur = cur->child[idx]; } return true; } private: bool isEnd; Trie *child[26]; }; /** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */