r*******n
发帖数: 3020 | | J****3
发帖数: 427 | | j*******t
发帖数: 223 | 3 sedgewick的书里有讲过很简单的trie。
public class TrieST {
private static final int R = 256; // extended ASCII
private Node root = new Node();
private static class Node {
private Object val;
private Node[] next = new Node[R];
}
public boolean contains(String key) {
return get(key) != null;
}
public Value get(String key) {
Node x = get(root, key, 0);
if (x == null) {
return null;
}
return (Value) x.val;
}
private Node get(Node x, String key, int d) {
if (x == null) {
return null;
}
if (d == key.length()) return x;
char c = key.charAt(d);
return get(x.next[c], key, d+1);
}
public void put(String key, Value val) {
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d) {
if (x == null) {
x = new Node();
}
if (d == key.length()) {
x.val = val;
return x;
}
char c = key.charAt(d);
x.next[c] = put(x.next[c], key, val, d+1);
return x;
}
} | s********u
发帖数: 1109 | 4 我觉得，在实际使用中，可以就写个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; }
}; | f**********s
发帖数: 115 | 5 我好几次需要写比较复杂的结构，都是一个劲找话说，说到没时间写了，也就不用写了
。。。有挂过，也有pass过，有点靠运气呵呵 | r*******n
发帖数: 3020 | | J****3
发帖数: 427 | | j*******t
发帖数: 223 | 8 sedgewick的书里有讲过很简单的trie。
public class TrieST {
private static final int R = 256; // extended ASCII
private Node root = new Node();
private static class Node {
private Object val;
private Node[] next = new Node[R];
}
public boolean contains(String key) {
return get(key) != null;
}
public Value get(String key) {
Node x = get(root, key, 0);
if (x == null) {
return null;
}
return (Value) x.val;
}
private Node get(Node x, String key, int d) {
if (x == null) {
return null;
}
if (d == key.length()) return x;
char c = key.charAt(d);
return get(x.next[c], key, d+1);
}
public void put(String key, Value val) {
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d) {
if (x == null) {
x = new Node();
}
if (d == key.length()) {
x.val = val;
return x;
}
char c = key.charAt(d);
x.next[c] = put(x.next[c], key, val, d+1);
return x;
}
} | s********u
发帖数: 1109 | 9 我觉得，在实际使用中，可以就写个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; }
}; | f**********s
发帖数: 115 | 10 我好几次需要写比较复杂的结构，都是一个劲找话说，说到没时间写了，也就不用写了
。。。有挂过，也有pass过，有点靠运气呵呵 | | | c********p
发帖数: 1969 | 11 mark.
一直想弄明白这个到底怎么实现，一直没实现。。。拖了半年。 | y******u
发帖数: 804 | | i******t
发帖数: 22541 | 13 word counts
【在 y******u 的大作中提到】
: 什么情况要用trie啊？
| p*u
发帖数: 136 | 14 WORD PUZZLE
给一个n*n的matrix，每个格子有一个字母(a~z)。另外给一个词典，有m个单词。
求matrix上的出现的单词
【在 r*******n 的大作中提到】
: 我面试还没遇到过用到Trie的题目。
| q****m
发帖数: 177 | 15 Node put(Node x, String key, Value val, int d) 里面的value 是什么用途？计数
吗？比如单词出现的次数？或者还要记录这个node对应的key？
【在 j*******t 的大作中提到】
: sedgewick的书里有讲过很简单的trie。
: public class TrieST {
: private static final int R = 256; // extended ASCII
: private Node root = new Node();
: private static class Node {
: private Object val;
: private Node[] next = new Node[R];
: }
: public boolean contains(String key) {
: return get(key) != null;
| p*****2
发帖数: 21240 | 16 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..] | x*****0
发帖数: 452 | | b****f
发帖数: 138 | |
|
