208. 实现 Trie (前缀树)||Trie字典树模板

题目：https://leetcode.cn/problems/implement-trie-prefix-tree/description/

以前的板子写得太丑陋了，重新写一份> <

因为是leetcode上的题目，所以是核心代码模式。

字典树（Trie）原理：（因为我语言表达能力不行，所以以下内容来源于小美AI机器人> <）

字典树（Trie）是一种用于高效存储和检索字符串集合的数据结构，特别适用于前缀匹配。它是一种多叉树，其中每个节点代表一个字符。

### 字典树的结构

1. **节点（Node）**：
- 每个节点代表一个字符。
- 根节点通常不包含字符，用于开始操作。
- 每个节点可以有多个子节点，每个子节点代表下一个字符。

2. **边（Edge）**：
- 边连接两个节点，表示从一个字符到下一个字符的转移。

3. **叶节点（Leaf Node）**：
- 叶节点表示一个完整的字符串结束。

### 字典树的基本操作

#### 1. 插入（Insert）

将一个字符串插入到字典树中。

**步骤**：
1. 从根节点开始。
2. 对于要插入的字符串中的每个字符，检查当前节点是否有对应的子节点。
3. 如果有，移动到对应的子节点；如果没有，创建一个新的子节点。
4. 重复步骤2和3，直到处理完字符串中的所有字符。
5. 将最后一个节点标记为单词结束（isEndOfWord = true）。

**示例**：
插入单词 "cat" 和 "car"。
```
(root)
/
c
/ \
a a
/ \
t r
```

#### 2. 查找（Search）

查找一个字符串是否存在于字典树中。

**步骤**：
1. 从根节点开始。
2. 对于要查找的字符串中的每个字符，检查当前节点是否有对应的子节点。
3. 如果有，移动到对应的子节点；如果没有，返回false。
4. 重复步骤2和3，直到处理完字符串中的所有字符。
5. 检查最后一个节点是否标记为单词结束。如果是，返回true；否则，返回false。

**示例**：
查找单词 "cat"。
```
(root)
/
c
/
a
/
t (isEndOfWord = true)
```

#### 3. 前缀查找（Prefix Search）

查找是否存在以指定前缀开头的字符串。

**步骤**：
1. 从根节点开始。
2. 对于要查找的前缀中的每个字符，检查当前节点是否有对应的子节点。
3. 如果有，移动到对应的子节点；如果没有，返回false。
4. 重复步骤2和3，直到处理完前缀中的所有字符。
5. 如果处理完所有字符，返回true。

**示例**：
查找前缀 "ca"。
```
(root)
/
c
/
a (存在前缀 "ca")

代码解释：

1. TrieNode 结构体：
- children：使用 `unordered_map` 存储子节点，键是字符，值是指向子节点的指针。
- isEndOfWord：布尔值，标记当前节点是否为单词的结束。
- 构造函数 TrieNode()：初始化 `isEndOfWord` 为 `false`。

2. Trie 类：
- root：根节点，不包含字符。
- insert 方法：插入单词，通过遍历单词的每个字符，如果当前节点没有对应的子节点，则创建一个新的子节点，最后将最后一个节点标记为单词结束。
- search 方法：查找单词，通过遍历单词的每个字符，如果当前节点没有对应的子节点，则返回 `false`。最后检查当前节点是否为单词结束。
- startsWith 方法：前缀查找，通过遍历前缀的每个字符，如果当前节点没有对应的子节点，则返回 `false`。否则返回 `true`。

 1 struct TrieNode{
 2     unordered_map<char,TrieNode*>children;
 3     bool isEndOfWord;
 4     TrieNode():isEndOfWord(0){}
 5 };
 6 class Trie {
 7 private:
 8     TrieNode* root;
 9 public:
10     Trie() {
11         root=new TrieNode();
12     }
13     void insert(const string&word) {
14         TrieNode* node=root;
15         for(auto c:word){
16             if(node->children.find(c)==node->children.end()){
17                 node->children[c]=new TrieNode();
18             }
19             node=node->children[c];
20         }
21         node->isEndOfWord=1;
22     }
23     bool search(const string&word) {
24         TrieNode* node=root;
25         for(char c:word){
26             if(node->children.find(c)==node->children.end())return 0;
27             node=node->children[c];
28         }
29         return node->isEndOfWord;
30     }
31     bool startsWith(const string&prefix) {
32         TrieNode* node=root;
33         for(char c:prefix){
34             if(node->children.find(c)==node->children.end())return 0;
35             node=node->children[c];
36         }
37         return 1;
38     }
39 };
40 
41 /**
42  * Your Trie object will be instantiated and called as such:
43  * Trie* obj = new Trie();
44  * obj->insert(word);
45  * bool param_2 = obj->search(word);
46  * bool param_3 = obj->startsWith(prefix);
47  */

by:AlenaNuna