要求实现一个字典树(Trie),又称为前缀树(Prefix Tree),字典树是一种很实用的数据结构。
字典树主要有如下三点性质:
- 根节点不包含字符,除根节点外每个节点只包含一个字符。
- 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
- 每个节点的所有子节点包含的字符串不相同。
如何存储孩子,一般有三种方法:
- 对每个结点开一个字母集大小的数组,对应的下标是儿子所表示的字母,内容则是这个儿子对应的位置(例如指向这个儿子的指针);
- 每个结点挂一个链表(或一个动态增长的数组),按一定顺序记录所有儿子;
- 使用左儿子右兄弟表示法记录这棵树。
三种方法,各有特点。第一种易实现,但实际的空间要求较大;第二种,较易实现,空间要求相对较小,但比较费时;第三种,空间要求最小,但相对费时且不易写。
由于题目说了只可能是小写字母,所以字母集大小就为26,下面代码我们就按照方法一来写。
另外在实现节点类时需要加一个bool型的属性is_last_letter
,代表这个字母是否是某个单词的结尾,即是否是叶子节点。
struct TrieNode{
bool is_last_letter; // 是否是某个单词的结尾, 即是叶子
char letter; // 其实是多余的, 因为我们可以通过其父节点知道当前节点的字符
vector<TrieNode *>next; // 孩子们
TrieNode(char cc): is_last_letter(false), letter(cc),
next(vector<TrieNode *>(26, NULL)){}
};
class Trie {
private:
TrieNode *root;
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode('\0'); // 根节点不包含字符
root -> is_last_letter = true;
}
/** Inserts a word into the trie. */
void insert(string word) {
if(word.empty()) return;
TrieNode *pre = root, *p = NULL;
for(int i = 0; i < word.size(); i++){
p = (pre -> next)[word[i] - 'a'];
if(!p){ // 没找到, 插入即可
p = new TrieNode(word[i]);
(pre -> next)[word[i] - 'a'] = p;
}
pre = p;
}
p -> is_last_letter = true;
}
// 返回word最后一个字母对应的在树中的节点指针
TrieNode *final_char(string word){
TrieNode *pre = root, *p = NULL;
for(int i = 0; i < word.size(); i++){
p = (pre -> next)[word[i] - 'a'];
if(!p) return NULL;
pre = p;
}
return p;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode *tmp = final_char(word);
return tmp && tmp -> is_last_letter;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return final_char(prefix) != NULL;
}
};