...
void insert(string word)：插入字符串word。bool search(string word)：返回字符串word是否存在于前缀树中。bool startWith(string prefix)：返回指定的前缀是否存在于前缀树中。vector<string> listStartWith(string prefix)：返回指定前缀的全部字符串。这个接口也可以设计成返回出现次数最多的前n个字符串。
以下是一个字典树的模板：以下是一个精简版的字典树的模板：
| 代码块 |
|---|
class Trie {
private:
int nxt[100000][26] = {0}; vector<Trie*> children// 使用数组来保存树结构，最大支持100000个结点
int cnt = 0;
bool isEndexist[100000] = {0};
public:
Trie* searchPrefix() {}
void insert(string prefixword) {
Trie*int nodep = this0;
for (charauto ch : prefixword) {
ch -= 'a';
if (node->children(!nxt[p][ch] == nullptr) {
return nullptrnxt[p][ch] = ++cnt;
}
nodep = node->childrennxt[p][ch];
}
exist[p] return= node1;
}
public:
Trie() : children(26), isEnd(false) {}
void insertbool search(string word) {
Trie*int nodep = this0;
for (charauto ch : word) {
ch -= 'a';
if (node->children(!nxt[p][ch] == nullptr) {
node->children[ch] = new Trie()return false;
}
nodep = node->childrennxt[p][ch];
}
node->isEnd = truereturn exist[p];
}
bool searchstartsWith(string wordprefix) {
Trie*int nodep = this->searchPrefix(word); 0;
for(auto ch : prefix) {
return node != nullptr &&ch node->isEnd= 'a';
}
bool startsWith(string prefixif(!nxt[p][ch]) {
return this->searchPrefix(prefix) != nullptr false;
}
p = nxt[p][ch];
}
return true;
}
}; |
例题：