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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 什么情况要用trie啊?
| p*u 发帖数: 136 | 14 WORD PUZZLE
给一个n*n的matrix,每个格子有一个字母(a~z)。另外给一个词典,有m个单词。
求matrix上的出现的单词
【在 r*******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我面试还没遇到过用到Trie的题目。
| q****m 发帖数: 177 | 15 Node put(Node x, String key, Value val, int d) 里面的value 是什么用途?计数
吗?比如单词出现的次数?或者还要记录这个node对应的key?
【在 j*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | |
|