s*******8
发帖数: 12734 | 1 有很多 字串， 经常要作的操作有 ， 插入， 删除， 清空，
查询以某前缀字串开头的所有的字串
查询以某前缀字串开头的所有的字串的个数
查询前缀字串开头的字串的所有 可能的下一个字母
例如
[abc, abd, abe]
input ab
return [c, d, e]
要求使3个查寻操作的时间上最优， 插入， 删除， 清空，的性能表现可以牺牲
那种数据结构实现比较好。 |
l*****a
发帖数: 14598 | 2
这个需要查吗?
Trie
【在 s*******8 的大作中提到】
: 有很多 字串， 经常要作的操作有 ， 插入， 删除， 清空，
: 查询以某前缀字串开头的所有的字串
: 查询以某前缀字串开头的所有的字串的个数
: 查询前缀字串开头的字串的所有 可能的下一个字母
: 例如
: [abc, abd, abe]
: input ab
: return [c, d, e]
: 要求使3个查寻操作的时间上最优， 插入， 删除， 清空，的性能表现可以牺牲
: 那种数据结构实现比较好。
|
p*****2
发帖数: 21240 | 3 这么勤奋？
【在 l*****a 的大作中提到】
:
: 这个需要查吗?
: Trie
|
s*******8
发帖数: 12734 | 4 如果这么简单，我就不问了，我实现的就trie, 有人说可以用 STL现成的container
【在 l*****a 的大作中提到】
:
: 这个需要查吗?
: Trie
|
s*******8
发帖数: 12734 | 5 没有说清除，要查询的是前缀字串开头的字串的所有 可能的下一个字母
例如
[abc, abd, abe]
input ab
return [c, d, e]
【在 l*****a 的大作中提到】
:
: 这个需要查吗?
: Trie
|
M*******p
发帖数: 18 | 6 好
：有很多 字串， 经常要作的操作有 ， 插入， 删除， 清空，
：查询以某前缀字串开头的所有的字串 |
l*****a
发帖数: 14598 | 7 这个用trie不work吗?
【在 s*******8 的大作中提到】
: 没有说清除，要查询的是前缀字串开头的字串的所有 可能的下一个字母
: 例如
: [abc, abd, abe]
: input ab
: return [c, d, e]
|
s*******8
发帖数: 12734 | 8 work 阿，
这个查询用trie很容易实现，直接遍历子指针，都不用递归，或者DFS
但是我的意思是如果不用 trie,怎么实现。。。
【在 l*****a 的大作中提到】
: 这个用trie不work吗?
|
l*****a
发帖数: 14598 | 9 你问"茴"子的四种写法?
【在 s*******8 的大作中提到】
: work 阿，
: 这个查询用trie很容易实现，直接遍历子指针，都不用递归，或者DFS
: 但是我的意思是如果不用 trie,怎么实现。。。
|
s*******8
发帖数: 12734 | 10 不是我非要问茴字，是有人问除了trie， 能不能直接用STL的某个container
【在 l*****a 的大作中提到】
: 你问"茴"子的四种写法?
|
Q**F
发帖数: 995 | 11 插入， 删除， 清空，的性能表现可以牺牲的话，是不是用2个map比较好？
任何插入的string，用它所有的前缀做成这两个map的key
一个map的value用一个vector记录所有以该key为前缀的字符串，这个主要用来做1，2
的操作， 另外一个map的value用一个26位长的数组来记录下一个字符及个数，这个用
来做3的操
作。
当删除一个字符串的时候，根据字符串的所有前缀删除第一个map中所有的该字符串。
第二个map的中含有该字符串的前缀的下一个字符的个数减少1
当然，这样会用到巨量空间。如果改用指针的话是不是会节约空间。
map > map1
map > map2; |
s*******8
发帖数: 12734 | 12 恩，这个可以，就是浪费空间。 每一个长度为N的字串，都要2N个 map entry
2
【在 Q**F 的大作中提到】
: 插入， 删除， 清空，的性能表现可以牺牲的话，是不是用2个map比较好？
: 任何插入的string，用它所有的前缀做成这两个map的key
: 一个map的value用一个vector记录所有以该key为前缀的字符串，这个主要用来做1，2
: 的操作， 另外一个map的value用一个26位长的数组来记录下一个字符及个数，这个用
: 来做3的操
: 作。
: 当删除一个字符串的时候，根据字符串的所有前缀删除第一个map中所有的该字符串。
: 第二个map的中含有该字符串的前缀的下一个字符的个数减少1
: 当然，这样会用到巨量空间。如果改用指针的话是不是会节约空间。
: map > map1
|
