把数据都存在一个TrieNode数组里,只保存其指向关系。
class TrieNode {
public:
bool end;
vector<int> son;
TrieNode() {
end = false;
son = vector<int>(26, -1);
}
};
class Trie {
public:
vector<TrieNode> tree;
Trie() {
tree.push_back(TrieNode());
}
bool query(string& s) {
int idx = 0;
for(char c : s) {
int to = tree[idx].son[c - 'a'];
if (to == -1) return false;
idx = to;
}
return tree[idx].end;
}
void insert(string &s) {
int idx = 0;
for (char c : s) {
if (tree[idx].son[c - 'a'] == -1) {
tree[idx].son[c - 'a'] = tree.size();
tree.push_back(TrieNode());
}
idx = tree[idx].son[c - 'a'];
}
tree[idx].end = true;
}
};
标签:end,idx,TrieNode,tree,son,int,模板,字典
From: https://www.cnblogs.com/FlyingLight/p/18309699