LeetCode 热门题目 100 | 图论（三）

目录

1 前缀树

1.1 什么是前缀树

1.2 如何构建前缀树

2 208. 实现 Trie（前缀树）

菜鸟做题，语言是 C++

1 前缀树

1.1 什么是前缀树

被广泛认可的前缀树 也被称为字典式检索结构或分支表。它被定义为一种专门用于从字符串数据集中快速定位特定键的过程的数据结构。每个节点代表一个字符。路径代表一条完整的字符串信息。这种高效的数据结构广泛应用于自动补全、拼写校对和自然语言处理等多个领域。

1.2 如何构建前缀树

根据前缀树的定义，其节点的结构应该为：

 class Trie {

    
 private:
    
     vector<Trie *> children;
    
     bool isEnd;
    
 }

• Trie 节点代表单个字符
• children字段存储所有可能后续单字符
• isEnd字段标记当前字符是否是某个单词的末尾

因此，在这里我们将前缀树定义为 Trie 类的原因在于它不仅能够实现基本功能，并且还提供了其他功能或操作。

假设我们需要存储 apple 和 app 这两个单词，则可以构建如下 Trie：

![](https://ad.itadn.com/c/weblog/blo