这次开字典树
作用：高效地存储和查找字符串集合的数据结构
功能：存储、查找
复杂度：O(len(str))
照例先贴视频
视频中代码的参考价值不大，以以下的代码为准
数组定义
vector<vector<int>> son; // 每个节点是一个长度为26的vector
vector<int> cnt; // 以当前节点结尾的单词数量第一个数组用于存储从节点 p 沿着字母 u 走到下一个节点的编号，如果是 0 就代表没有这条路。
同时二维数组实现O(1)查询
第二个数组为尾标记。尾标记为0代表没有单词以当前字母结尾
节点初始化
Trie() {
// 初始化根节点: 创建一个大小为26、全0的vector
son.emplace_back(26, 0);
cnt.push_back(0);
}初始化son：根节点默认没有走向任何字母的路，需要insert操作添加
初始化cnt：根节点不可能是任何一个单词的结尾
插入函数
void insert(const string& str)
{
int p = 0; // 从根节点（编号0）开始
for (char ch : str) // 遍历字符串中的每一个字符
{
int u = ch - 'a'; // 将字符映射为0~25的数字
if (son[p][u] == 0) // 如果当前节点p的u号子节点不存在
{
son.emplace_back(26, 0); // 创建新节点并初始化son数组
cnt.push_back(0); // 新节点的单词计数初始为0
son[p][u] = (int)son.size() - 1; // 从节点p到字母u的坐标更新为新节点
}
p = son[p][u]; // 移动到子节点，继续处理下一个字符
}
cnt[p]++; // 单词多出现了一次
}查询函数
int query(const string& str) const
{
int p = 0; // 从根节点（编号0）开始查找
for (char ch : str) // 依次遍历字符串中的每个字符
{
int u = ch - 'a'; // 将字符映射为0~25的数字（a->0, b->1, ..., z->25）
if (son[p][u] == 0) // 如果当前节点的对应子节点不存在
return 0; //单词不在树中，返回0
p = son[p][u]; // 移动到子节点，继续匹配下一个字符
}
return cnt[p]; // 所有字符匹配完毕，返回以该节点结尾的单词数量（即该单词出现的次数）
}完整封装
struct Trie {
vector<vector<int>> son; // 每个节点是一个长度为26的vector
vector<int> cnt; // 以当前节点结尾的单词数量
Trie() {
// 初始化根节点: 创建一个大小为26、全0的vector
son.emplace_back(26, 0);
cnt.push_back(0);
}
void insert(const string& str) {
int p = 0;
for (char ch : str) {
int u = ch - 'a';
if (son[p][u] == 0) {
// 创建新节点: 添加一个大小为26、全0的vector
son.emplace_back(26, 0);
cnt.push_back(0);
son[p][u] = (int)son.size() - 1;
}
p = son[p][u];
}
cnt[p]++;
}
int query(const string& str) const {
int p = 0;
for (char ch : str) {
int u = ch - 'a';
if (son[p][u] == 0) return 0;
p = son[p][u];
}
return cnt[p];
}
};
评论（0）
暂无评论