序言
虽然算法很难，但不应该就放弃。这是一个学习笔记，希望你们喜欢~
先自己尝试写，大概十几分钟仍然写不出来
看思路，再尝试跟着思路写
仍然写不出来，再看视频
b站up视频推荐：爱学习的饲养员
leetcode其他文章：
数组篇：
链表篇：
从小白开始刷算法 ListNode 链表篇 leetcode.203
从小白开始刷算法 ListNode 链表篇 leetcode.206
队列篇
从小白开始刷算法 ListNode 链表篇 leetcode.933
栈篇
从小白开始刷算法 Stack 栈篇 leetcode.496
哈希篇
从小白开始刷算法 Hash 哈希篇 leetcode.217
从小白开始刷算法 Hash 哈希篇 leetcode.705
树篇
从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144
从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94
从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94
堆篇
从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215
小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692
双指针篇
二分法篇
滑动窗口篇
递归篇
分治法篇
回溯法篇
dfs篇
bfs篇
并查集篇
记忆化搜索篇
动态规划篇
前缀树篇
难度：中等
题目：
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
题目来源：力扣（LeetCode）
前缀树介绍
前缀树（Trie树），也称为字典树或单词查找树，是一种用于高效存储和检索字符串集合的数据结构。它通过将字符串拆分成字符序列，并将每个字符作为树的节点，将整个字符串存储在树中。
前缀树的特点是共享公共前缀。在树的根节点到任意节点的路径上，构成的字符序列就是该节点所代表的字符串。这样的设计使得在前缀树中查找字符串或者插入新字符串的操作非常高效。
前缀树常用于解决字符串相关的问题，如字符串的前缀匹配、单词搜索、自动补全和词频统计等。它的主要优势是在大量字符串集合中快速定位目标字符串，具有较高的查询效率和空间利用率。
在前缀树的实现中，每个节点包含一个字符和指向子节点的指针。通常使用数组、哈希表或其他数据结构来存储子节点。另外，可以在每个节点上保存额外的信息，如单词的频率、是否为单词的结束节点等。
前缀树的时间复杂度和空间复杂度取决于存储的字符串数量和字符串的平均长度。在一般情况下，前缀树的查询操作的时间复杂度为O(k)，其中k为目标字符串的长度。而前缀树的空间复杂度与存储的字符串数量和字符串的平均长度成正比。
思路
Trie的常见操作包括插入（insert）、搜索（search）和前缀匹配（startsWith）：
- insert操作：将一个字符串逐个字符地插入到Trie中。从根节点开始，检查当前字符是否已经存在于子节点中，如果存在，则继续向下遍历；如果不存在，则创建一个新的子节点。最后，在字符串的最后一个字符节点上标记为终止节点，表示该路径构成了一个完整的字符串。
- search操作：从根节点开始，逐个字符地遍历字符串。如果字符存在于当前节点的子节点中，则继续向下遍历；如果字符不存在于子节点中，或者遍历到了字符串的最后一个字符但是当前节点没有标记为终止节点，则表示字符串不存在于Trie中。
- startsWith操作：从根节点开始，逐个字符地遍历前缀字符串。如果字符存在于当前节点的子节点中，则继续向下遍历；如果字符不存在于子节点中，或者遍历到了前缀字符串的最后一个字符，则表示前缀不存在于Trie中。
Trie的优点是能够高效地存储大量的字符串集合，并且支持快速的字符串搜索和前缀匹配。它的时间复杂度主要取决于字符串的长度，而与存储的字符串数量无关。
然而，Trie也有一些缺点。它可能占用较多的内存空间，尤其是在存储大量长字符串时。此外，构建和维护Trie树的操作可能较为复杂，并且对于包含大量不同字符的字符串集合，Trie树的深度可能会很大，导致操作性能下降。
因此，在实际应用中，需要根据具体的需求和场景来选择合适的数据结构，权衡Trie的优点和缺点。
// 仅是我的思路代码，leetcode上大神更厉害 class TrieNode { private TrieNode[] children; private boolean isEndOfWord; public TrieNode() { // 26个英文字母 children = new TrieNode[26]; isEndOfWord = false; } public void insert(String word) { TrieNode curr = this; for (char c : word.toCharArray()) { //计算字符 c 在字母表中的索引,Trie树用于存储小写字母， //字母表中的字符从 'a' 到 'z'，用整数索引 0 到 25 表示。 //ASCII编码中，小写字母 'a' 的整数值是 97 int index = c - 'a'; if (curr.children[index] == null) { curr.children[index] = new TrieNode(); } curr = curr.children[index]; } curr.isEndOfWord = true; } public boolean search(String word) { TrieNode node = searchPrefix(word); return node != null && node.isEndOfWord; } public boolean startsWith(String prefix) { TrieNode node = searchPrefix(prefix); return node != null; } private TrieNode searchPrefix(String prefix) { TrieNode curr = this; for (char c : prefix.toCharArray()) { int index = c - 'a'; if (curr.children[index] == null) { return null; } curr = curr.children[index]; } return curr; } } class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { root.insert(word); } public boolean search(String word) { return root.search(word); } public boolean startsWith(String prefix) { return root.startsWith(prefix); } }
