AcWing 937. 单词查找树
原题链接
简单
作者:
王小强
,
2021-02-04 12:42:59
,
所有人可见
,
阅读 397
前缀树 == 字典树 == 单词查找树(模版代码)
#include <iostream>
#include <memory>
#include <vector>
using namespace std;
class Trie {
public:
/** Initialize your data structure here. */
Trie() : count_(1), root_(new TrieNode()) {}
/** Inserts a word into the trie. */
void insert(const string& word) {
auto p = root_.get();
for (const auto& c : word) {
if (!p->children[c - 'A']) {
p->children[c - 'A'] = new TrieNode();
++count_;
}
p = p->children[c - 'A'];
}
p->is_word = true;
}
int get_count() const {
return count_;
}
private:
struct TrieNode {
TrieNode() : is_word(false), children(26, nullptr) {}
~TrieNode() {
for (const auto& child : children) delete child;
}
bool is_word;
vector<TrieNode*> children;
};
std::unique_ptr<TrieNode> root_;
int count_;
};
int main(void) {
Trie trie;
string word;
while (getline(cin, word))
trie.insert(word);
cout << trie.get_count() << endl;
return 0;
}