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 的大作中提到】
: 先是看到一个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 的大作中提到】
: 先是看到一个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 的大作中提到】
: 楼主能把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 的大作中提到】
: 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 的大作中提到】
: 先是看到一个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 的大作中提到】
: 先是看到一个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 的大作中提到】
: 楼主能把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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 我自己发的帖子耶。。。。
|
w*********e
发帖数: 207 | |
j********l
发帖数: 325 | |
|
|
j**********3
发帖数: 3211 | |
c******n
发帖数: 4965 | 32 你能不能把原题paste 出来， 这样如果题目不清楚，胡乱做完全是走火入魔
【在 y*****e 的大作中提到】
: 先是看到一个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 的大作中提到】
: 先是看到一个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了 |
