leetcode:208. 实现 Trie (前缀树)
程序员文章站
2022-07-15 16:17:19
...
208. 实现 Trie (前缀树)
前缀树的思想:
- 边表示字符(其实边和点都行)
- 点的含义表示是否为单词结尾,也可另外再赋予其他含义
图来自于:https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/208-shi-xian-trie-qian-zhui-shu-bao-gua-insert-sea/
-
insert
过程- 先进行遍历,把前面所有的公共前缀遍历完
- 然后在后面把剩下的字符加上
- 最后
end=true
,表示这里是一个单词的结尾
-
query
过程- 先进行遍历,把前面所有的公共前缀遍历完
- 遍历完公共前缀,这时候
end=true
,说明前面有这个字符串insert
- 否则,没有
struct node{
node(){
end = false;
}
vector<pair<node*, char>> edge;
bool end;
};
class Trie {
public:
node* root;
/** Initialize your data structure here. */
Trie() {
root = new node;
}
/** Inserts a word into the trie. */
void insert(string word) {
int k = 0;
node* nod = root;
for(int i = 0; i < nod->edge.size()&&k < word.size(); i ++){
if(nod->edge[i].second == word[k]){
nod = nod->edge[i].first;
i = -1;
k ++;
}
}
while(k < word.size()){
node* a = new node;
nod->edge.push_back(make_pair(a, word[k++]));
nod = a;
}
nod->end = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
int k = 0;
node* nod = root;
for(int i = 0; i < nod->edge.size()&&k < word.size(); i ++){
if(nod->edge[i].second == word[k]){
nod = nod->edge[i].first;
i = -1;
k ++;
}
}
if(k == word.size()&&nod->end) return true;
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
int k = 0;
node* nod = root;
for(int i = 0; i < nod->edge.size()&&k < prefix.size(); i ++){
if(nod->edge[i].second == prefix[k]){
nod = nod->edge[i].first;
i = -1;
k ++;
}
}
if(k == prefix.size()) return true;
return false;
}
};
/**
* 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);
*/
其他解法
细节上,还可以有很多不同的地方,比如可以直接把node
的定义直接放在Trie
中,那么每一个节点拿出来都可以看作一个Trie
。
也可以用数组来表示每个节点的后继,数组只用26个空间。这样在查找是否有相应后继的时候速度加快,不用遍历,但是牺牲了空间。这种写法可以参考面试题 17.17. 多次搜索
上一篇: 146. LRU缓存机制
下一篇: codevs 1083