【面试经典 150 | 字典树】实现 Trie (前缀树)

本文主要是介绍【面试经典 150 | 字典树】实现 Trie (前缀树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【前缀树】【树形结构】

---

题目来源

208. 实现 Trie (前缀树)

---

解题思路

方法一：前缀树

前缀树也叫字典树，是一种树形数据结构，用于高效地存储和检索字符串数据集中的键，方便查找某个字符是否存在或者查找某个前缀是否存在。

通常具有插入前缀、检索前缀以及判断字典树中是否存在某个前缀的功能。

代码

class TrieNode{
public:bool end; // 1表示从根到它是一个完整字典中的串TrieNode *next[26];TrieNode(): end(false){memset(next, 0, sizeof(next));}};class Trie {
private:TrieNode* root;
public:Trie(): root(new TrieNode()) {}void insert(string word) {// 从根结点开始插入TrieNode* now = root;for(int i = 0; i < word.size(); ++i){int child = word[i] - 'a';if(nullptr == now->next[child]){now->next[child] = new TrieNode();}now = now->next[child];}now->end = true;}// 判断前缀树中是否有完整的前缀 wordbool search(string word) {TrieNode* now = root;for(int i = 0; i < word.size(); ++i){int child = word[i] - 'a';if(nullptr == now->next[child]){return false;}now = now->next[child];}return now->end;}// 判断前缀树中是否有完整的前缀是以 prefix 开始的bool startsWith(string prefix) {TrieNode* now = root;for(int i = 0; i < prefix.size(); ++i){int child = prefix[i] - 'a';if(nullptr == now->next[child]){return false;}now = now->next[child];}return true;}
};

复杂度分析

时间复杂度：初始化的时间复杂度为 $O(1)$，其余操作都是 $O(|S|)$，其中 $|S|$ 是每次插入或查询的字符串的长度。

空间复杂度：$O(\mid T\mid \cdot \Sigma )$，其中 $|T|$ 为所有插入字符串的长度之和，$\Sigma$ 为字符集的大小，本题 $\Sigma =26$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。

这篇关于【面试经典 150 | 字典树】实现 Trie (前缀树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---