一、概念
字典树(Trie)用于判断字符串是否存在或者是否具有某种字符串前缀。
包含三个单词 "sea","sells","she" 的 Trie 长这样:
为什么需要用字典树解决这类问题呢?假如我们有一个储存了近万个单词的字典,即使我们
使用哈希,在其中搜索一个单词的实际开销也是非常大的,且无法轻易支持搜索单词前缀。然而
由于一个英文单词的长度n 通常在10 以内,如果我们使用字典树,则可以在O(n)——近似O(1)
的时间内完成搜索,且额外开销非常小。
二、题解
class Trie { private: vector<Trie*> children; bool isEnd; // 标记该节点是否是单词的最后一个字母 public: // 每个节点都含26个指向Trie的指针 Trie(): children(26), isEnd(false) {} void insert(string word) { Trie* nownode = this; // this表示当前Trie对象的地址(Trie* obj = new Trie();) for (char ch: word) { ch -= 'a'; if (nownode->children[ch] == nullptr) { nownode->children[ch] = new Trie(); } nownode = nownode->children[ch]; } nownode->isEnd = true; // 最后一个字母设为true } bool search(string word) { Trie* nownode = this; for (char ch: word) { ch -= 'a'; if (nownode->children[ch] == nullptr) { return false; } nownode = nownode->children[ch]; } return nownode->isEnd; // 若nownode->isEnd = false, 则表明字典树中并无该单词,(未到结尾) } bool startsWith(string prefix) { Trie* nownode = this; for (char ch: prefix) { ch -= 'a'; if (nownode->children[ch] == nullptr) { return false; } nownode = nownode->children[ch]; } return 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); */
参考视频:
https://leetcode.cn/problems/implement-trie-prefix-tree/solution/gua-he-xin-shou-peng-you-de-shi-pin-ti-j-fhvw/
标签:ch,word,Trie,nownode,children,字典 From: https://www.cnblogs.com/spacerunnerZ/p/17132384.html