（中等）剑指Offer II 062.实现前缀树 Java

**前缀树（Trie）的实现**
=====================================前缀树（Trie），又称为字典树，是一种常见的数据结构，用于存储和检索字符串集合。它通过将所有可能的前缀连接起来，形成一个多叉树，从而高效地支持快速查找、插入和删除等操作。

**Java实现**
------------下面是 Java 实现的 Trie 类：

javapublic class Trie {
 // 前缀树节点类 private static class Node {
 boolean isEndOfWord; // 是否为单词结尾 Map children; // 子节点映射 public Node() {
 this.isEndOfWord = false;
 this.children = new HashMap<>();
 }
 }

 private Node root; // 前缀树根节点 public Trie() {
 this.root = new Node();
 }

 /**
 * 插入一个字符串 *
 * @param word 字符串 */
 public void insert(String word) {
 Node node = root;
 for (char c : word.toCharArray()) {
 if (!node.children.containsKey(c)) {
 node.children.put(c, new Node());
 }
 node = node.children.get(c);
 }
 node.isEndOfWord = true;
 }

 /**
 * 检索一个字符串是否存在 *
 * @param word 字符串 * @return 是否存在 */
 public boolean search(String word) {
 Node node = root;
 for (char c : word.toCharArray()) {
 if (!node.children.containsKey(c)) {
 return false;
 }
 node = node.children.get(c);
 }
 return node.isEndOfWord;
 }

 /**
 * 检索一个前缀是否存在 *
 * @param prefix 前缀 * @return 是否存在 */
 public boolean startsWith(String prefix) {
 Node node = root;
 for (char c : prefix.toCharArray()) {
 if (!node.children.containsKey(c)) {
 return false;
 }
 node = node.children.get(c);
 }
 return true;
 }

 // 测试用例 public static void main(String[] args) {
 Trie trie = new Trie();
 trie.insert("apple");
 trie.insert("app");
 System.out.println(trie.search("apple")); // true System.out.println(trie.search("app")); // true System.out.println(trie.startsWith("ap")); // true }
}

**代码注释**
-------------

* `Node`类：代表 Trie 的一个节点，包含两个属性：`isEndOfWord`（是否为单词结尾）和 `children`（子节点映射）。
* `Trie`类：代表 Trie 本身，包含三个方法：`insert`（插入一个字符串）、`search`（检索一个字符串是否存在）和 `startsWith`（检索一个前缀是否存在）。

**使用示例**
-------------

1. 创建一个 Trie 实例。
2. 插入一些字符串，如 `"apple"` 和 `"app"`.
3. 检索这些字符串的存在，如 `search("apple")` 和 `search("app")`.
4. 检索某个前缀是否存在，如 `startsWith("ap")`.

**注意**
----

* Trie 的空间复杂度取决于所存储的字符串集合的大小和分布。
* Trie 的时间复杂度取决于查找、插入或删除操作涉及的节点数量。

**参考资料**
--------------

* [Wikipedia - Trie]( />* [GeeksforGeeks - Trie Data Structure](