【设计-1】208.实现Trie (前缀树)

题目描述Trie发音类似 try或者说前缀树是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补全和拼写检查。请你实现 Trie 类Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中返回true即在检索之前已经插入否则返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix返回true否则返回false。示例输入[Trie, insert, search, search, startsWith, insert, search] [[], [apple], [apple], [app], [app], [app], [app]]输出[null, null, true, false, true, null, true]解释Trie trie new Trie(); trie.insert(apple); trie.search(apple); // 返回 True trie.search(app); // 返回 False trie.startsWith(app); // 返回 True trie.insert(app); trie.search(app); // 返回 True解题思路方法一字典树 (26 叉树)核心思路Trie 的结构root ├── a │ └── p │ └── p │ └── l │ └── e (isEnd true) └── b └── ...每个节点包含children[26]26 个子节点指针对应 a-zisEnd是否是某个单词的结尾操作逻辑操作逻辑insert从根开始逐个字符向下走不存在就创建节点最后标记isEnd truesearch从根开始逐个字符向下走走不到返回false走完检查isEndstartsWith和search一样但不需要检查isEnd代码实现class Trie { private: struct TrieNode { TrieNode* children[26]; bool isEnd; TrieNode() { for (int i 0; i 26; i) { children[i] nullptr; } isEnd false; } }; TrieNode* root; public: Trie() { root new TrieNode(); } void insert(string word) { TrieNode* node root; for (char c : word) { int index c - a; if (node-children[index] nullptr) { node-children[index] new TrieNode(); } node node-children[index]; } node-isEnd true; } bool search(string word) { TrieNode* node root; for (char c : word) { int index c - a; if (node-children[index] nullptr) { return false; } node node-children[index]; } return node-isEnd; } bool startsWith(string prefix) { TrieNode* node root; for (char c : prefix) { int index c - a; if (node-children[index] nullptr) { return false; } node node-children[index]; } return true; } };复杂度分析设L是字符串长度。操作时间复杂度空间复杂度insertO(L)O(L)最坏情况新建 L 个节点searchO(L)O(1)startsWithO(L)O(1)整体-O(总字符数 × 26)关键细节1. 为什么用数组而不是哈希表TrieNode* children[26]; // 数组数组访问 O(1)比哈希表更快题目限定小写字母26 个足够如果字符集更大可以用unordered_mapchar, TrieNode*2.search和startsWith的区别// search: 必须是一个完整的单词 return node-isEnd; // startsWith: 只要是前缀就行 return true;关键search检查isEndstartsWith不检查。3. 为什么用isEnd标记因为一个单词可能是另一个单词的前缀插入 apple 后再插入 app 如果不标记 isEndsearch(app) 无法区分 app 是完整单词还是 apple 的前缀4. 内存泄漏问题~Trie() { deleteNode(root); } void deleteNode(TrieNode* node) { for (int i 0; i 26; i) { if (node-children[i]) { deleteNode(node-children[i]); } } delete node; }LeetCode 上不要求但实际工程中需要释放内存。方法二哈希表为什么用哈希表对比维度数组children[26]哈希表unordered_map适用字符集仅小写字母任意字符集空间占用每个节点固定 26 个指针只存实际存在的子节点访问速度O(1)O(1) 平均代码复杂度简单中等优势如果字符集很大如 Unicode或者子节点很稀疏哈希表更省空间。代码实现class Trie { private: struct TrieNode { unordered_mapchar, TrieNode* children; // 哈希表存子节点 bool isEnd; TrieNode() : isEnd(false) {} }; TrieNode* root; public: Trie() { root new TrieNode(); } void insert(string word) { TrieNode* node root; for (char c : word) { // 如果子节点不存在创建 if (node-children.find(c) node-children.end()) { node-children[c] new TrieNode(); } node node-children[c]; } node-isEnd true; } bool search(string word) { TrieNode* node root; for (char c : word) { if (node-children.find(c) node-children.end()) { return false; } node node-children[c]; } return node-isEnd; } bool startsWith(string prefix) { TrieNode* node root; for (char c : prefix) { if (node-children.find(c) node-children.end()) { return false; } node node-children[c]; } return true; } };更简洁的写法用countvoid insert(string word) { TrieNode* node root; for (char c : word) { if (!node-children.count(c)) { node-children[c] new TrieNode(); } node node-children[c]; } node-isEnd true; } bool search(string word) { TrieNode* node root; for (char c : word) { if (!node-children.count(c)) return false; node node-children[c]; } return node-isEnd; } bool startsWith(string prefix) { TrieNode* node root; for (char c : prefix) { if (!node-children.count(c)) return false; node node-children[c]; } return true; }具体过程示例插入apple后root └── children[a] → node_a └── children[p] → node_p1 └── children[p] → node_p2 └── children[l] → node_l └── children[e] → node_e (isEndtrue)哈希表只存实际存在的字符不像数组要开 26 个位置。复杂度分析设L是字符串长度。操作时间复杂度空间复杂度insertO(L)O(L)searchO(L)O(1)startsWithO(L)O(1)整体-O(总字符数)空间复杂度对比数组O(总字符数 × 26)哈希表O(总字符数)关键细节1.findvscountvs[]写法行为children.find(c) children.end()判断是否存在children.count(c)返回 0 或 1children[c]不存在时会创建默认值慎用注意children[c]在键不存在时会插入一个默认值nullptr可能改变哈希表大小。2. 为什么哈希表更省空间数组每个节点固定 26 个指针共 26 × 8 208 字节哈希表只存实际存在的子节点稀疏时节省大量空间3. 什么时候用数组什么时候用哈希表场景推荐仅小写字母数组更快字符集大Unicode哈希表子节点稀疏哈希表追求极致速度数组数组 vs 哈希表对比对比维度数组哈希表时间复杂度O(1)O(1) 平均空间复杂度O(26 × 节点数)O(实际子节点数)适用字符集固定小字符集任意字符集代码复杂度简单中等推荐度⭐⭐⭐⭐⭐小写字母⭐⭐⭐⭐通用