y*****e 发帖数: 712 | 1 先是看到一个facebook的题,说是implement search autocompletion,用trie。
然后又看到一题implement getWords(), 和hasPrefix()
我在网上找了好久,没看到比较完整的实现,大概思路两个,一个是用array或
Linkedlist把children连起来,另一个是用hashmap连起来。。。
第一个思路大概是这样的
https://community.oracle.com/thread/2070706
但这个实现的也不严谨。。。
没办法,我把在角落里吃灰的clrs拿出来,竟然没有找到trie的implementation!!
我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
较严谨完整呢?
非常感谢! |
r*****b 发帖数: 310 | 2 It is not a good idea to use trie to implement auto-completeion, espeically
at the facebook scale. Trie consumes a lot of memory, and the pionter-
jumping will lead to a lot of cache miss, and significantly slow down the
cpu.
【在 y*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先是看到一个facebook的题,说是implement search autocompletion,用trie。 : 然后又看到一题implement getWords(), 和hasPrefix() : 我在网上找了好久,没看到比较完整的实现,大概思路两个,一个是用array或 : Linkedlist把children连起来,另一个是用hashmap连起来。。。 : 第一个思路大概是这样的 : https://community.oracle.com/thread/2070706 : 但这个实现的也不严谨。。。 : 没办法,我把在角落里吃灰的clrs拿出来,竟然没有找到trie的implementation!! : 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比 : 较严谨完整呢?
|
d****d 发帖数: 699 | |
v****a 发帖数: 236 | |
j**********g 发帖数: 77 | |
b******i 发帖数: 914 | 6 楼主能把getWords()和hasPrefix()具体是要干什么描述一下吗
虽然从字面可以猜出大概,但是有题目会好一点,谢谢
【在 y*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先是看到一个facebook的题,说是implement search autocompletion,用trie。 : 然后又看到一题implement getWords(), 和hasPrefix() : 我在网上找了好久,没看到比较完整的实现,大概思路两个,一个是用array或 : Linkedlist把children连起来,另一个是用hashmap连起来。。。 : 第一个思路大概是这样的 : https://community.oracle.com/thread/2070706 : 但这个实现的也不严谨。。。 : 没办法,我把在角落里吃灰的clrs拿出来,竟然没有找到trie的implementation!! : 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比 : 较严谨完整呢?
|
y*****e 发帖数: 712 | 7 面经里也没有说。。。我自己理解的是
boolean hasPrefix(String s), 其实就是search, 看看这个string s是不是存在在
trie里面
List getWords(String s), 是找以s开头的所有词,比如给ab,return abc,
abcd, abfg等等。
【在 b******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主能把getWords()和hasPrefix()具体是要干什么描述一下吗 : 虽然从字面可以猜出大概,但是有题目会好一点,谢谢
|
d******v 发帖数: 801 | |
k*********n 发帖数: 6 | |
a****r 发帖数: 87 | 10 C++ R-way trie implementation. Coursera princeton algorithm II 讲的很详细。
const int N = 26;
struct TrieNode{
int val;
vector link;
TrieNode(int x=-1): val(x), link(N){}
};
class Trie{
public:
Trie(){
root = new TrieNode;
}
void put(string &key, int val){
put(root, key, val, 0);
}
int get(string &key){
TrieNode *t = get(root, key, 0);
if(t) return t->val;
else return -1;
}
void remove(string &key){
remove(root, key, 0);
}
private:
TrieNode *root;
void remove(TrieNode *&root, string &key, int d){
if(!root) return;
if(key.length() == d) root->val = -1;
int k = key[d]-'a';
remove(root->link[k], key, d+1);
if(isEmptyNode(root->link[k])){
if(root->link[k]) delete root->link[k];
root->link[k] = nullptr;
return;
}
}
bool isEmptyNode(TrieNode *root){
if(!root) return true;
if(root->val != -1) return false;
for(int i = 0; i < N; i++){
if(root->link[i]) return false;
}
return true;
}
void put(TrieNode *&root, string &key, int val, int d){
if(!root) root = new TrieNode;
if(key.length() == d){
root->val = val;
return;
}
int k = key[d]-'a';
put(root->link[k], key, val, d+1);
}
TrieNode *get(TrieNode *root, string &key, int d){
if(!root) return nullptr;
if(d == key.length()) return root;
int k = key[d]-'a';
return get(root->link[k], key, d+1);
}
}; |
|
|
l***i 发帖数: 1309 | 11 facebook hackcup round1 has a trie problem so you can see the world's first
class programmer's implementation. |
y*****e 发帖数: 712 | 12 要不要这么拼。。。。一流选手的代码俺怎么看的懂。。。
first
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : facebook hackcup round1 has a trie problem so you can see the world's first : class programmer's implementation.
|
y*****e 发帖数: 712 | 13 先是看到一个facebook的题,说是implement search autocompletion,用trie。
然后又看到一题implement getWords(), 和hasPrefix()
我在网上找了好久,没看到比较完整的实现,大概思路两个,一个是用array或
Linkedlist把children连起来,另一个是用hashmap连起来。。。
第一个思路大概是这样的
https://community.oracle.com/thread/2070706
但这个实现的也不严谨。。。
没办法,我把在角落里吃灰的clrs拿出来,竟然没有找到trie的implementation!!
我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
较严谨完整呢?
非常感谢! |
r*****b 发帖数: 310 | 14 It is not a good idea to use trie to implement auto-completeion, espeically
at the facebook scale. Trie consumes a lot of memory, and the pionter-
jumping will lead to a lot of cache miss, and significantly slow down the
cpu.
【在 y*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先是看到一个facebook的题,说是implement search autocompletion,用trie。 : 然后又看到一题implement getWords(), 和hasPrefix() : 我在网上找了好久,没看到比较完整的实现,大概思路两个,一个是用array或 : Linkedlist把children连起来,另一个是用hashmap连起来。。。 : 第一个思路大概是这样的 : https://community.oracle.com/thread/2070706 : 但这个实现的也不严谨。。。 : 没办法,我把在角落里吃灰的clrs拿出来,竟然没有找到trie的implementation!! : 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比 : 较严谨完整呢?
|
d****d 发帖数: 699 | |
v****a 发帖数: 236 | |
j**********g 发帖数: 77 | |
b******i 发帖数: 914 | 18 楼主能把getWords()和hasPrefix()具体是要干什么描述一下吗
虽然从字面可以猜出大概,但是有题目会好一点,谢谢
【在 y*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先是看到一个facebook的题,说是implement search autocompletion,用trie。 : 然后又看到一题implement getWords(), 和hasPrefix() : 我在网上找了好久,没看到比较完整的实现,大概思路两个,一个是用array或 : Linkedlist把children连起来,另一个是用hashmap连起来。。。 : 第一个思路大概是这样的 : https://community.oracle.com/thread/2070706 : 但这个实现的也不严谨。。。 : 没办法,我把在角落里吃灰的clrs拿出来,竟然没有找到trie的implementation!! : 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比 : 较严谨完整呢?
|
y*****e 发帖数: 712 | 19 面经里也没有说。。。我自己理解的是
boolean hasPrefix(String s), 其实就是search, 看看这个string s是不是存在在
trie里面
List getWords(String s), 是找以s开头的所有词,比如给ab,return abc,
abcd, abfg等等。
【在 b******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主能把getWords()和hasPrefix()具体是要干什么描述一下吗 : 虽然从字面可以猜出大概,但是有题目会好一点,谢谢
|
d******v 发帖数: 801 | |
|
|
k*********n 发帖数: 6 | |
a****r 发帖数: 87 | 22 C++ R-way trie implementation. Coursera princeton algorithm II 讲的很详细。
const int N = 26;
struct TrieNode{
int val;
vector link;
TrieNode(int x=-1): val(x), link(N){}
};
class Trie{
public:
Trie(){
root = new TrieNode;
}
void put(string &key, int val){
put(root, key, val, 0);
}
int get(string &key){
TrieNode *t = get(root, key, 0);
if(t) return t->val;
else return -1;
}
void remove(string &key){
remove(root, key, 0);
}
private:
TrieNode *root;
void remove(TrieNode *&root, string &key, int d){
if(!root) return;
if(key.length() == d) root->val = -1;
int k = key[d]-'a';
remove(root->link[k], key, d+1);
if(isEmptyNode(root->link[k])){
if(root->link[k]) delete root->link[k];
root->link[k] = nullptr;
return;
}
}
bool isEmptyNode(TrieNode *root){
if(!root) return true;
if(root->val != -1) return false;
for(int i = 0; i < N; i++){
if(root->link[i]) return false;
}
return true;
}
void put(TrieNode *&root, string &key, int val, int d){
if(!root) root = new TrieNode;
if(key.length() == d){
root->val = val;
return;
}
int k = key[d]-'a';
put(root->link[k], key, val, d+1);
}
TrieNode *get(TrieNode *root, string &key, int d){
if(!root) return nullptr;
if(d == key.length()) return root;
int k = key[d]-'a';
return get(root->link[k], key, d+1);
}
}; |
l***i 发帖数: 1309 | 23 facebook hackcup round1 has a trie problem so you can see the world's first
class programmer's implementation. |
y*****e 发帖数: 712 | 24 要不要这么拼。。。。一流选手的代码俺怎么看的懂。。。
first
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : facebook hackcup round1 has a trie problem so you can see the world's first : class programmer's implementation.
|
s********x 发帖数: 81 | 25 其实就是tree,只是多了一个flag标志,表示这是一个end,表示suffix的终结 |
C****r 发帖数: 401 | 26
espeically
what should be the right way then?
【在 r*****b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : It is not a good idea to use trie to implement auto-completeion, espeically : at the facebook scale. Trie consumes a lot of memory, and the pionter- : jumping will lead to a lot of cache miss, and significantly slow down the : cpu.
|
y*****e 发帖数: 712 | |
J*******o 发帖数: 741 | 28
楼主怎么感叹起自己发帖来了。。。
【在 y*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我自己发的帖子耶。。。。
|
w*********e 发帖数: 207 | |
j********l 发帖数: 325 | |
|
|
j**********3 发帖数: 3211 | |
c******n 发帖数: 4965 | 32 你能不能把原题paste 出来, 这样如果题目不清楚,胡乱做完全是走火入魔
【在 y*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先是看到一个facebook的题,说是implement search autocompletion,用trie。 : 然后又看到一题implement getWords(), 和hasPrefix() : 我在网上找了好久,没看到比较完整的实现,大概思路两个,一个是用array或 : Linkedlist把children连起来,另一个是用hashmap连起来。。。 : 第一个思路大概是这样的 : https://community.oracle.com/thread/2070706 : 但这个实现的也不严谨。。。 : 没办法,我把在角落里吃灰的clrs拿出来,竟然没有找到trie的implementation!! : 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比 : 较严谨完整呢?
|
p*****3 发帖数: 488 | 33
波妹,又换id了?
【在 y*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先是看到一个facebook的题,说是implement search autocompletion,用trie。 : 然后又看到一题implement getWords(), 和hasPrefix() : 我在网上找了好久,没看到比较完整的实现,大概思路两个,一个是用array或 : Linkedlist把children连起来,另一个是用hashmap连起来。。。 : 第一个思路大概是这样的 : https://community.oracle.com/thread/2070706 : 但这个实现的也不严谨。。。 : 没办法,我把在角落里吃灰的clrs拿出来,竟然没有找到trie的implementation!! : 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比 : 较严谨完整呢?
|
k****e 发帖数: 16 | |
h******b 发帖数: 12 | 35 mark
刚做了lc新题,每个node里面加了children的hashmap(用于快速决定放弃继续向下搜
索)和arraylist(用于储存重复的children),结果TLE了 |