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

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

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：前缀树
写在最后

写在前面

本专栏专注于分析与讲解【面试经典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 ∣$ 是每次插入或查询的字符串的长度。