208. 实现 Trie (前缀树)
难度中等700
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
提示:
1 <= word.length, prefix.length <= 2000
word
和prefix
仅由小写英文字母组成insert
、search
和startsWith
调用次数 总计 不超过3 * 104
次 ``` class Trie { private: //一个trie节点有两个结构,一个是指针,指向子节点的字母映射表,一个是是否是叶 vectorchildren; bool isEnd; Trie* searchPrefix(string prefix){ Trie* node = this;
for(char ch : prefix){
ch -= 'a';
if(node->children[ch] == nullptr){
return nullptr;
}
node = node->children[ch];
}
return node;
} public: /* Initialize your data structure here. / Trie() : children(26), isEnd(false){}
/* Inserts a word into the trie. / void insert(string word) {
Trie* node = this;
for(auto ch : word){
ch -= 'a';
if(node->children[ch] == nullptr){
node->children[ch] = new Trie();
}
node = node->children[ch];
}
node->isEnd = true;
}
/* Returns if the word is in the trie. / bool search(string word) {
Trie* node = this->searchPrefix(word);
return node != nullptr && node->isEnd;
}
/* Returns if there is any word in the trie that starts with the given prefix. / bool startsWith(string prefix) {
return this->searchPrefix(prefix) != nullptr;
} };
/**
- 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); */
<a name="SV2sx"></a>
#### [720. 词典中最长的单词](https://leetcode-cn.com/problems/longest-word-in-dictionary/)
class Trie { private: bool isEnd; vector
children; public: Trie() { this->children = vector<Trie* >(26, nullptr);
this->isEnd = false;
} bool insert(const string &word){
Trie * node = this;
for(const auto &ch : word){
int index = ch - 'a';
if(node->children[index] == nullptr){
node->children[index] = new Trie();
}
node = node->children[index];
}
node->isEnd = true;
return true;
}
bool search(string word){
Trie* node = this;
for(const auto &ch : word){
int index = ch - 'a';
//这里用isEnd为true保证是有前缀出现过的
if(node->children[index] == nullptr || !node->children[index]->isEnd){
return false;
}
node = node->children[index];
}
return node->isEnd && node != nullptr;
} }; class Solution { public: string longestWord(vector
& words) { Trie trie;
for(auto & s: words){
trie.insert(s);
}
string ans = "";
for(auto &s: words){
if(trie.search(s)){
//这里保证了,返回的是字典序较小的
if(s.size() > ans.size() || (s.size() == ans.size() && s < ans)){
ans = s;
}
}
}
return ans;
} }; ```