一、问题描述：
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树）是一种用于存储关联数组的数据结构，特别适用于字符串的存储与查找。它是一种树形结构，其中每个节点代表一个字符串的字符，从根节点到叶节点的路径表示一个字符串。前缀树的特点是，所有从根节点到某一节点的路径上的字符连接起来都表示相同的前缀。示例如下：
-
以下是前缀树的基本性质和操作：
①节点结构：前缀树的节点通常包含一个指向子节点的指针数组，以及一个标志位用于表示节点是否是某个字符串的结尾。
②插入操作：将一个字符串插入到前缀树中，需要从根节点开始，逐字符遍历字符串，对应地创建或者沿着已有的路径移动，直到字符串的末尾，将最后一个字符所在的节点标记为字符串结尾。
③搜索操作：给定一个字符串，从根节点开始，逐字符遍历字符串，沿着对应的路径移动，如果在某一步找不到对应的子节点，或者遍历完字符串后发现最后一个字符所在的节点没有标记为字符串结尾，则表示该字符串不存在于前缀树中。
④前缀匹配：给定一个前缀，可以在前缀树中查找所有以该前缀开头的字符串。 -
数据结构定义：
- Trie 类中包含两个主要成员变量：
①children 数组：用于存储每个节点的子节点，数组长度为 26，对应英文字母表中的每个字母。
②isEnd 标志位：表示当前节点是否为一个字符串的结尾。 - 构造函数：初始化 Trie 树的根节点，将子节点数组 children 初始化为长度为 26 的数组，并将所有元素初始化为 null，同时将 isEnd 初始化为 false。
- 插入操作 (insert 方法)：用于将字符串插入到 Trie 树中。
①从根节点开始遍历字符串中的每个字符。
②对于每个字符，计算其在 children 数组中的索引位置。
③如果对应位置的子节点为空，则创建一个新的子节点，并将当前节点移动到该子节点。
④最终将字符串的最后一个字符所对应的节点的 isEnd 标志位设置为 true，表示该节点为一个字符串的结尾。 - 搜索操作 (search 方法)：用于搜索是否存在完整的字符串。
首先调用 searchPrefix 方法，根据给定的字符串搜索到对应的节点。
如果找到节点且该节点的 isEnd 标志位为 true，则表示找到了完整的字符串，返回 true；否则返回 false。 - 前缀搜索操作 (startsWith 方法)：用于搜索是否存在以指定前缀开头的字符串。
调用 searchPrefix 方法搜索前缀，如果找到对应的节点，则说明该前缀存在，返回 true；否则返回 false。 - 前缀搜索具体实现 (searchPrefix 方法)：用于搜索给定前缀所对应的节点。
①从根节点开始遍历前缀中的每个字符。
②对于每个字符，计算其在 children 数组中的索引位置。
③如果对应位置的子节点为空，则表示该前缀不存在，直接返回 null。
④如果找到对应的子节点，则将当前节点移动到该子节点。
⑤最终返回找到的最后一个节点，即表示找到了前缀对应的节点。
三、代码示例：
class Trie {
private Trie[] children; // 子节点数组，存储下一级节点
private boolean isEnd; // 标记当前节点是否为字符串的结尾
public Trie() {
children = new Trie[26]; // 26个字母，每个位置对应一个子节点
isEnd = false; // 初始化节点不是字符串的结尾
}
public void insert(String word) {
Trie node = this; // 从根节点开始插入
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a'; // 计算字符在子节点数组中的索引
if (node.children[index] == null) {
node.children[index] = new Trie(); // 如果子节点不存在，则创建一个新的子节点
}
node = node.children[index]; // 移动到下一级节点
}
node.isEnd = true; // 新插入的数据，记录该节点的状态，刚好是一个字符串的结尾
}
public boolean search(String word) {
Trie node = searchPrefix(word); // 先根据前缀搜索到对应的节点
return node != null && node.isEnd; // 如果节点存在且为字符串的结尾，则表示找到了完整的字符串
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null; // 只需判断前缀是否存在即可
}
public Trie searchPrefix(String prefix) {
Trie node = this; // 从根节点开始搜索
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a'; // 计算字符在子节点数组中的索引
if (node.children[index] == null) {
return null; // 如果没有对应的子节点，表示前缀不存在
}
node = node.children[index]; // 移动到下一级节点
}
return node; // 返回找到的最后一个节点
}
}
- 时间复杂度：
插入操作（insert）：对于每个要插入的字符串，需要遍历字符串的每个字符，因此时间复杂度为O(m)，其中m是字符串的长度。
搜索操作（search）：对于每个要搜索的字符串，需要遍历字符串的每个字符，因此时间复杂度为O(m)，其中m是字符串的长度。
前缀匹配操作（startsWith）：对于每个要匹配的前缀字符串，需要遍历字符串的每个字符，因此时间复杂度为O(m)，其中m是前缀字符串的长度。 - 空间复杂度：
前缀树的空间复杂度主要取决于存储的字符串数量和字符串的长度。在最坏情况下，每个节点都可能有26个子节点，因此空间复杂度为O(26^m * n)，其中m是字符串的平均长度，n是字符串的数量。但实际上，大部分节点并不会有那么多子节点，因此实际的空间复杂度会小于这个上界。
四、补充与总结：
前缀树的应用包括但不限于：①自动补全②拼写检查③字典实现④IP 路由查找⑤前缀匹配搜索引擎
前缀树的实现可以采用多种方式，包括基于数组、基于指针、基于哈希表等。在实际应用中，需要根据具体情况选择最合适的实现方式。