1. 简介

前缀树是一种数据结构，常用来字符搜索。

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);*/