实现 Trie (前缀树)
- 难度： 中等
- 通过率： 35.6%
- 题目链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
题目描述
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
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
说明:
- 你可以假设所有的输入都是由小写字母
a-z构成的。 - 保证所有输入均为非空字符串。
解法：
前缀树，没什么好说的。这里使用了智能指针，性能稍稍受损。像树这样的结构，还是使用普通指针比较好。只需要在析构函数中释放内存即可。
class Trie {
public:
struct Node;
struct Node{
Node():tail(false){}
bool tail;
shared_ptr<Node> next['z'-'a'+1];
};
/** Initialize your data structure here. */
Trie() {
root = make_shared<Node>();
}
/** Inserts a word into the trie. */
void insert(string word) {
shared_ptr<Node> p = root;
for(char ch : word){
int index = ch - 'a';
if(p->next[index] == nullptr){
p->next[index] = make_shared<Node>();
}
p = p->next[index];
}
p->tail = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
shared_ptr<Node> p = root;
for(char ch : word){
int index = ch - 'a';
if(p->next[index] == nullptr){
return false;
}
p = p->next[index];
}
return p->tail;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
shared_ptr<Node> p = root;
for(char ch : prefix){
int index = ch - 'a';
if(p->next[index] == nullptr){
return false;
}
p = p->next[index];
}
return true;
}
private:
shared_ptr<Node> root;
};