f*******t
发帖数: 7549 | 1 struct Trie
{
Trie();
~Trie();
Trie *children[26];
bool isEnd;
};
Trie::Trie()
{
for(int i = 0; i < 26; i++)
children[i] = NULL;
isEnd = false;
}
Trie::~Trie()
{
for(int i = 0; i < 26; i++) {
if(children[i]) {
delete children[i];
children[i] = NULL;
}
}
}
void TrieInsert(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid line\n");
return;
}
Trie *cur ... 阅读全帖 |
|
p*****2
发帖数: 21240 | 2 trie =
isword: false
add = (trie, word)->
if word.length is 0
trie.isword = true
else
ch = word[0]
trie[ch] = {isword:false} unless trie[ch]?
add(trie[ch], word[1..])
exists = (trie, word)->
return trie.isword if word.length is 0
ch = word[0]
trie[ch]? and exists trie[ch], word[1..] |
|
i**********e
发帖数: 1145 | 3 1) array trie definition
struct Trie {
// pointer to its 26 children.
// children[i] == NULL means that particular child doesn't exist.
Trie *children[26];
bool end; // marker to indicate if current letter is end of a word.
};
2) linked list trie definition
struct Trie {
// pointer to its first child.
Trie *son;
// pointer to its sibling node.
Trie *next;
};
For 1) -- array trie definition, the insert(const char *s) function is easy
to write. For 2), is a little more tricky to writ... 阅读全帖 |
|
S*******C
发帖数: 822 | 4 Input: WORD.LST
And a randomly picked 1000 words from the same WORD.LST for querying.
This is a list of > 100,000 English words. It is sorted alphabetically.
Your task is to create a Compact Trie. Each node of trie will contain,
(1) A leading character (possibly empty (for root))
(2) String Label (possibly null (for root))
(3) Boolean IsWord , indicating whether the current node represents a whole
word or not (this is helpful when one word may be a prefix of another).
(4) Node *RightSIbling
(5)... 阅读全帖 |
|
a****r
发帖数: 87 | 5 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){... 阅读全帖 |
|
a****r
发帖数: 87 | 6 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){... 阅读全帖 |
|
S*******C
发帖数: 822 | 7 Input: WORD.LST
And a randomly picked 1000 words from the same WORD.LST for querying.
This is a list of > 100,000 English words. It is sorted alphabetically.
Your task is to create a Compact Trie. Each node of trie will contain,
(1) A leading character (possibly empty (for root))
(2) String Label (possibly null (for root))
(3) Boolean IsWord , indicating whether the current node represents a whole
word or not (this is helpful when one word may be a prefix of another).
(4) Node *RightSIbling
(5)... 阅读全帖 |
|
i**********e
发帖数: 1145 | 8 Trie 的插入和查找是 O(N), N = 字符串的长度。
Trie 是 prefix tree 的简称。
网上有很多关于 trie 的教程，相信你可以很快就掌握。
至于 suffix tree 就比较复杂，面试一般都不太问。至少不会变态到叫你写代码。 |
|
|
i**********e
发帖数: 1145 | 9 The space complexity depend on how many words you insert into the trie, and
also the common prefixes they all shared. In addition, it also depends on
how you represent a trie node's children. For example, representing its
children as a linked list is more space efficient than an array of children
nodes.
In all cases, the trie is more efficient in terms of space and speed
compared to hash table for the purposes of checking prefixes of a string. |
|
c********t
发帖数: 5706 | 10 经常看到面经里说统计查询字符串的频率用trie结构。
比如统计所有用户在google search上的查询字符串的频率。
我的疑惑就是memory能存下这样一个trie结构吗？如果能需要多大？我的想法是就算字
符串长度最多255，那也是 26^255数量级吧。
同样，有的设计，把字典单词都放在一个trie里，我也很困惑。
求解释。
多谢！ |
|
s********u
发帖数: 1109 | 11 我觉得，在实际使用中，可以就写个node，就是自带一个bool值，一个char值，和一个
vector。其他的函数，可以写成global或者solution类里面。否则你既要写
node，还要写trie类。
比如boggle game那个题，明显就是不用trie自己的search比较好，因为每次只需要
search一个char就行了。用trie自己的，就要search一个string。
struct TrieNode {
char mContent;
bool mMarker;
vector mChildren;
Node(char *c) { mContent = c; mMarker = false; }
}; |
|
s********u
发帖数: 1109 | 12 我觉得，在实际使用中，可以就写个node，就是自带一个bool值，一个char值，和一个
vector。其他的函数，可以写成global或者solution类里面。否则你既要写
node，还要写trie类。
比如boggle game那个题，明显就是不用trie自己的search比较好，因为每次只需要
search一个char就行了。用trie自己的，就要search一个string。
struct TrieNode {
char mContent;
bool mMarker;
vector mChildren;
Node(char *c) { mContent = c; mMarker = false; }
}; |
|
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
发帖数: 712 | 15 先是看到一个facebook的题，说是implement search autocompletion，用trie。
然后又看到一题implement getWords(), 和hasPrefix()
我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
Linkedlist把children连起来，另一个是用hashmap连起来。。。
第一个思路大概是这样的
https://community.oracle.com/thread/2070706
但这个实现的也不严谨。。。
没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
较严谨完整呢？
非常感谢！ |
|
r*****b
发帖数: 310 | 16 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. |
|
r****o
发帖数: 1950 | 17 我对trie一直不是很懂，
如果要在n个单词中查某个单词(长度为m个字母)的话，
为什么不能把这n个单词组成一个binary search tree呢？这样平均复杂度是O(lgn)。
而用trie查的话复杂度是O(m)。
这样lgn
这个问题可能很弱，欢迎拍砖。 |
|
a*d
发帖数: 47 | 18 in binary search tree, each comparison compares entire key.
But for trie, at each node it only compares one bit.
For long key, such as strings, it makes a big difference.
In other word, lg(n) of m character comparison for BST.
O(m) comparison for trie. |
|
i**********e
发帖数: 1145 | 19 You don't need to create a trie that store all words.
If you're finding a rectangle of size mxn, you only need to store all words
of length m and length n only in the trie.
the
in |
|
i**********e
发帖数: 1145 | 20 Here are some statistics on how much time and memory to create a trie with
all words in the dictionary:
Each node has 26 trie nodes. (children represented as an array)
Time: < 1sec, Memory: 45 MB
Each node has a pointer to the head of its children. (children represented
as linked list)
Time: < 1sec, Memory: 10 MB
the
in |
|
d*******l
发帖数: 338 | 21 我觉得suffix tree可以认为是把一个字符串的所有suffix放进一个trie中，并压缩掉
度为1的节点得到的结果。
所以原则上能用其中一个地方也能用另一个，差别在复杂度上。不过现实中trie还能写
写，suffix tree的O(n)实现不太可能写出来。最多也就能嘴上说说。 |
|
I******k
发帖数: 378 | 22 这两个可以用同样的数据结构实现吧， 感觉suffix tree就是trie的一种特殊情况，从
不同的位置开始到字符串末尾得到的substr建起来的trie. 最简单的实现下面这种就可
以了吧：
struct trieNode
{
trieNode *child[26]; // suppose only contain a-z
char *str; // characters in this node
}；
各位有什么看法？ |
|
h*******e
发帖数: 1377 | 23 trie 放不下可以放在别的机器里分布式存储吧~~ trie 存储本来就比较费空间 |
|
g*******s
发帖数: 2963 | 24 一般的trie只有leaf才能代表一个合法word么？
比如“tea” 和 “tear”都是合法word，那我建立trie的时候因该怎样插入tea？
在boggle的时候，如何让程序在搜到tea以后继续dfs搜索可能出现的tear？ |
|
A*********c
发帖数: 430 | 25 trie, compressed trie, tenary tree.
with |
|
|
|
y*****e
发帖数: 712 | 28 面经里也没有说。。。我自己理解的是
boolean hasPrefix(String s), 其实就是search, 看看这个string s是不是存在在
trie里面
List getWords(String s), 是找以s开头的所有词，比如给ab，return abc,
abcd, abfg等等。 |
|
l***i
发帖数: 1309 | 29 facebook hackcup round1 has a trie problem so you can see the world's first
class programmer's implementation. |
|
|
|
y*****e
发帖数: 712 | 32 面经里也没有说。。。我自己理解的是
boolean hasPrefix(String s), 其实就是search, 看看这个string s是不是存在在
trie里面
List getWords(String s), 是找以s开头的所有词，比如给ab，return abc,
abcd, abfg等等。 |
|
l***i
发帖数: 1309 | 33 facebook hackcup round1 has a trie problem so you can see the world's first
class programmer's implementation. |
|
l******0
发帖数: 244 | 34 Time complexity, the worst case is O(N) for HashMap and O(K), where N is the
number of entries in the map, and K is the length of the input String S.
What about space complexity? 由于 Trie 可以共享字符串，好像要节省存储空间，
看资料说 trie 比 hashmap 更耗空间。为什么？ |
|
j*t
发帖数: 184 | 35 这是trie吗? 应该是一个recursive search吧. |
|
l*****a
发帖数: 14598 | 36 就是建trie
每个节点有一个链表保存所有以（根到此节点路径）开头的单词
很直接。。 |
|
f*****w
发帖数: 2602 | 37 看了下不是很明白。 Trie的不同地方是key都在leaf上 我不明白为什么这样子跟DST
比起来好处
是什么？ 有能指教下的没有啊？ |
|
t**r
发帖数: 3428 | 38 还有，TRIE的 插入和查找都是 O(1) 我的理解多么 |
|
|
s*****y
发帖数: 897 | 40 How is the space complexity of the trie you create in the previous post:
求一道 面世题 的解答思路 |
|
s*****y
发帖数: 897 | 41 Ye. That is my question. Base on the input of that puzzle, it seems that the
trie will occupy a lot of memory as you create a tire for so many words in
a 1.6MB file.
I did not check carefully how similar are their prefix though.
and
children |
|
j********x
发帖数: 2330 | 42 完全两种东西，区别太明显
当然可以把suffix看成是compact suffix trie
。。。 |
|
O******i
发帖数: 269 | 43 要是被要求白板写trie的code怎么写？比如输入手机数字键，蹦出一系列匹配的单词，
比如2键上有abc三个字母。 |
|
n*******w
发帖数: 687 | 44 这是两个小问题吧。
先产生permutation，再去dictionary里边查。后者可以用trie存储字典。比较适合面
试白板的是前一部分。 |
|
k****n
发帖数: 369 | 45 依赖于数据结构的算法，尤其是trie这种东西，关键是把类的数据想好
然后把接口函数设计好，然后问面试官需要填哪个就写哪个
全写下来是不可能的，也没那么大白板 |
|
f**********n
发帖数: 10 | 46 rt. 貌似现场写代码实现trie还挺难的，也没什么约定俗成的接口什么的。大家说说应
该怎么办啊。。。 |
|
p*****2
发帖数: 21240 | 47 其实真的不难 我现在做简单题也用 就是为了练习
rt. 貌似现场写代码实现trie还挺难的，也没什么约定俗成的接口什么的。大家说说应
该怎么办啊。。。
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
|
|
I******k
发帖数: 378 | 49 trie同样一个node可以存一个字符串。suffix tree是一种特殊情况，应该有一些特殊
属性可以利用。wiki了一下Ukkonen algo，没看明白。 |
|
|
