【Hot 100】208. 实现 Trie (前缀树)

• 🙋‍♂️ 作者：海码007
• 📜 专栏：算法专栏
• 💥 标题：【Hot 100】208. 实现 Trie (前缀树)
• ❣️ 寄语：书到用时方恨少，事非经过不知难！

引言

实现 Trie (前缀树)

• 🎈 题目链接：
• 🎈 做题状态：

我的解题

首先需要理解前缀树的定义，前缀树是一颗多叉树，树根不存储字母。每一层可能存储26个不同的字母。然后每一个单词对应这个多叉树的一条路径，并且路径的结尾会标识是单词的结尾。

class Trie {
private:bool isEnd;Trie* next[26]; //指针数组，有26个小写字母public:Trie() {isEnd = false;memset(next, 0, sizeof(next));}// 插入一个单词void insert(string word) {// node指向根节点并向下遍历Trie* node = this;for (char c : word){// 判断当前这个字母是否在当前层存在，如果不存在则创建一个新的树。if (node->next[c-'a'] == nullptr){node->next[c-'a'] = new Trie();}node = node->next[c-'a'];   // 继续往下遍历}// 遍历到末尾后，需要标识 endnode->isEnd = true;}// 搜索当前单词是否存在，依次比较每个单词是否存在每一层中bool search(string word) {Trie* node = this;for (const char& c : word){if (node->next[c-'a'] == nullptr){return false;}node = node->next[c-'a'];}return node->isEnd; // 遍历到末尾后还需要判断是否是单词的结尾}// 判断这个前缀树是否包含 prefix 这个前缀bool startsWith(string prefix) {Trie* node = this;for (const char& c : prefix){if (node->next[c-'a'] == nullptr){return false;}node = node->next[c-'a'];}return true;}
};/*** 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);*/

代码解析

该代码实现了一个基本的前缀树（Trie）结构，支持插入、搜索和前缀匹配功能。以下是对代码的详细分析和优化建议：

---

代码思路分析

1. 数据结构设计：

   • isEnd：标记当前节点是否为单词的结尾。
   • next[26]：一个包含 26 个指针的数组，对应英文小写字母，用于构建字符到子节点的映射。

2. 核心方法：

   • 插入 (insert): 从根节点开始，逐字符向下遍历。若字符对应的子节点不存在，则创建新节点。遍历完成后，标记最后一个节点为单词结尾。
   • 搜索 (search): 检查单词是否存在且最后一个节点被标记为结尾。
   • 前缀匹配 (startsWith): 仅检查路径是否存在，无需判断结尾标记。

3. 正确性：

   • 逻辑正确，符合前缀树的标准实现。
   • 使用 memset 初始化指针数组，确保初始值为 nullptr。

---

优化建议

1. 内存泄漏问题

当前代码未释放动态分配的子节点，导致内存泄漏。需添加析构函数递归释放子节点：

~Trie() {for (int i = 0; i < 26; ++i) {delete next[i]; // 递归调用子节点的析构函数}
}

2. 使用智能指针优化内存管理

改用 std::unique_ptr 管理子节点，避免手动释放内存：

class Trie {
private:bool isEnd;std::array<std::unique_ptr<Trie>, 26> next; // 使用智能指针public:Trie() : isEnd(false) {} // 无需 memsetvoid insert(string word) {Trie* node = this;for (char c : word) {if (!node->next[c - 'a']) {node->next[c - 'a'] = std::make_unique<Trie>();}node = node->next[c - 'a'].get();}node->isEnd = true;}// search 和 startsWith 无需修改
};

3. 输入合法性校验（可选）

若需处理非法字符（如大写字母），可在插入/查询前添加校验：

void insert(string word) {for (char c : word) {if (c < 'a' || c > 'z') {throw std::invalid_argument("Invalid character");}}// 原插入逻辑
}

4. 其他优化

• 空间优化：使用压缩 Trie 树（如 Ternary Search Tree）减少内存占用，但会增加实现复杂度。
• 性能优化：当前时间复杂度为 O(L)（L 为字符串长度），已是最优，无需调整。

---

总结

代码逻辑正确，但存在内存泄漏问题。建议通过析构函数或智能指针优化内存管理。其他优化可根据实际需求选择。改进后的代码示例（使用智能指针）如下：

#include <memory>   // 用于智能指针 unique_ptr
#include <array>    // 用于固定大小的数组 array
#include <string>   // 用于字符串操作class Trie {
private:// 标记当前节点是否为某个单词的结尾bool isEnd;// 使用智能指针管理子节点，避免内存泄漏// 数组大小为26，对应英文小写字母a-zstd::array<std::unique_ptr<Trie>, 26> next;public:// 构造函数：初始化 isEnd 为 false，表示初始时不是单词结尾// 智能指针数组 next 会自动初始化为 nullptrTrie() : isEnd(false) { }/*** 插入一个单词到 Trie 树中* @param word 待插入的单词*/void insert(const std::string& word) {// 从根节点（this）开始遍历Trie* node = this;// 逐个字符处理for (char c : word) {// 计算字符对应的索引（a->0, b->1, ..., z->25）int idx = c - 'a';// 如果当前字符的子节点不存在，则创建新节点if (node->next[idx] == nullptr) {node->next[idx] = std::make_unique<Trie>();}// 移动到子节点继续处理node = node->next[idx].get();  // get() 获取裸指针}// 标记单词的最后一个字符节点为结尾node->isEnd = true;}/*** 搜索 Trie 树中是否存在某个单词* @param word 待搜索的单词* @return 如果单词存在且完整匹配（最后一个字符是结尾），返回 true；否则返回 false*/bool search(const std::string& word) {// 从根节点开始遍历Trie* node = this;// 逐个字符检查for (const char& c : word) {int idx = c - 'a';// 如果当前字符的子节点不存在，说明单词不存在if (node->next[idx] == nullptr) {return false;}// 移动到子节点继续检查node = node->next[idx].get();}// 检查最后一个字符是否被标记为单词结尾return node->isEnd;}/*** 检查 Trie 树中是否存在某个前缀* @param prefix 待检查的前缀* @return 如果前缀存在（不要求是完整单词），返回 true；否则返回 false*/bool startsWith(const std::string& prefix) {// 从根节点开始遍历Trie* node = this;// 逐个字符检查for (const char& c : prefix) {int idx = c - 'a';// 如果当前字符的子节点不存在，说明前缀不存在if (node->next[idx] == nullptr) {return false;}// 移动到子节点继续检查node = node->next[idx].get();}// 只要路径存在，无论是否是单词结尾，都返回 truereturn true;}
};