什么是 Trie (前缀树, 字典树) ?
1.Trie, 又称为前缀树, 或者字典树, 是一个树形的数据结构, 用于高效地存储和检索字符串数据; 说白了就是两个功能: 插入字符串和检索字符串, 其中检索字符串包括要搜索的字符串前缀是否在里面 (单词本身是它自己的一种前缀)
2.在实际应用中, 比如拼写检查或者自动补全就使用这样的数据结构
3.Trie 树中, 每个节点包括两个字段
(i). 指向子节点的指针数组 children, 例如对于纯英文的单词下, 就是一个 vector
(ii). bool 类型的字段指示是否为字符串的结尾, 比如 $isEnd$, 这个可以标记要搜索的单词是否是一个已经记录下来的单词
4.Trie 树插入字符串的功能如何实现? 插入字符时, 对于当前字符对应的子节点, 有两种情况:
(i). 子节点不存在, 创建一个子节点, 记录在 children 数组对应的位置上, 然后沿着指针移动到子节点, 继续搜索下一个字符
(ii). 子节点存在, 沿着指针移动到子节点, 继续搜索下一个字符
5.查找字符, 对于当前字符对应的子节点
(i). 子节点不存在, 说明 trie 中不包括该前缀, 返回空指针
(ii). 子节点存在, 沿着指针移动到子节点, 继续搜索下一个字符
重复以上, 直到返回空指针或者是搜索完待搜索前缀的最后一个字符: 如果可以搜到了前缀的末尾, 说明存在前缀; 另外如果 is_end == ture, 说明存在该字符串
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
class Trie {
private:
vector<Trie*> children; // 子节点指针, 指向的是 Trie 类型的孩子节点, 用一个数组
bool isEnd; // 标记已经是末尾
public:
Trie() {
children = vector<Trie*>(26, nullptr);
isEnd = false;
}
// 搜索前缀的函数: 实现核心搜索前缀的功能
// 如果前缀完全匹配, 返回非空的指针;
// 如果前缀匹配过程中没有匹配到, 直接返回空指针;
Trie* searchPrefix(string word) {
Trie* node = this;
for (char c: word) {
if (node->children[c - 'a'] == nullptr) {
return nullptr;
}
node = node->children[c - 'a'];
}
return node;
}
// 插入字符串的函数
// 遍历字符串
// 如果当前 children[ch] 已经开了指针, node 沿着指针搜索 node = node->children[c - 'a'];
// 如果当前 children[ch] 没有开指针, 那么 new 一个 Trie();
void insert(string word) {
Trie* node = this;
for (char c: word) {
if (node->children[c - 'a'] == nullptr) {
node->children[c - 'a'] = new Trie();
}
node = node->children[c - 'a'];
}
node->isEnd = true;
}
// 匹配前缀函数: 能搜到前缀
bool startsWith(string prefix) {
return searchPrefix(prefix) != nullptr;
}
// 匹配单词函数: 能搜到前缀, 且 idEnd 标记为 true
bool search(string word) {
Trie* node = searchPrefix(word);
return node != nullptr && node->isEnd == true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
转载请注明来源, from goldandrabbit.github.io
