s*****y
发帖数: 897 | 1 在careercup上面看到的，应该怎么解啊
If there is dictionary of words and you want to add new word into that
dictionary and u have to find whether that new word is combination of two
words which are already in dictionary
e.g you want to add newspaper then there are words news and paper in
dictionary you have find it with minimum compexity. I answered trie
structure but stucked with complexity then hash but he didn't satisfied | g*****e
发帖数: 282 | 2 how abt two layer hash?
news-> [1]
paper-> [2]
newspaer->[1]->[2]
【在 s*****y 的大作中提到】
: 在careercup上面看到的，应该怎么解啊
: If there is dictionary of words and you want to add new word into that
: dictionary and u have to find whether that new word is combination of two
: words which are already in dictionary
: e.g you want to add newspaper then there are words news and paper in
: dictionary you have find it with minimum compexity. I answered trie
: structure but stucked with complexity then hash but he didn't satisfied
| b******y
发帖数: 9224 | 3 not sure, seems like you could use hash table? | s********y
发帖数: 58 | 4 prefix tree, 在wiki里面搜trie大概能搜到把. | r******e
发帖数: 80 | 5 trie is good, i think. why he is not satisfied. If the length of the
string is k, then the complexity if k^2. | s*****g
发帖数: 5159 | 6 Trie is pretty good for this.
Suppose you are inserting newspaper.
You go through the trie (an up to 26 branching tree), you will stop at news,
and check the paper from the root of trip. On average the complexity is n.
In the worst case, suppose, all n, ne, new, news, newsp, newspa, newspap, ne
wspape, are all on your trie, you will have to look through all ewspaper, ws
paper, spaper, paper, aper, per, er, r, each look up takes n time and you ha
ve (n-1) checks. Total complexity will be n^2.
How would you do with hash, especially when n is small, the cost of hash is
pretty high, even thats an O(n) algorithm.
【在 s*****y 的大作中提到】
: 在careercup上面看到的，应该怎么解啊
: If there is dictionary of words and you want to add new word into that
: dictionary and u have to find whether that new word is combination of two
: words which are already in dictionary
: e.g you want to add newspaper then there are words news and paper in
: dictionary you have find it with minimum compexity. I answered trie
: structure but stucked with complexity then hash but he didn't satisfied
| s*****y
发帖数: 897 | 7 Thanks all very much. 我去看看trie | b***e
发帖数: 1419 | 8 搞两个tries, 一正一反，查两遍，比较长度，O(n).
news,
n.
newspap, ne
ewspaper, ws
you ha
is
【在 s*****g 的大作中提到】
: Trie is pretty good for this.
: Suppose you are inserting newspaper.
: You go through the trie (an up to 26 branching tree), you will stop at news,
: and check the paper from the root of trip. On average the complexity is n.
: In the worst case, suppose, all n, ne, new, news, newsp, newspa, newspap, ne
: wspape, are all on your trie, you will have to look through all ewspaper, ws
: paper, spaper, paper, aper, per, er, r, each look up takes n time and you ha
: ve (n-1) checks. Total complexity will be n^2.
: How would you do with hash, especially when n is small, the cost of hash is
: pretty high, even thats an O(n) algorithm.
| l***i
发帖数: 1309 | 9 How much time/space you would spend in building a trie, and update after you
insert you new word? The problem is not explicit about what data structures
are used to store the dict, or what operations it supports with what time
complexity. | m**q
发帖数: 189 | 10 好主意
是不是可以这样： 假设原字符串为s，长度为l，先在正的trie里面查找s,
直到遇到一个完整的单词，记下长度a；然后在反的trie里面查找，每次
遇到一个单词记下位置，直到查找的长度等于l-a。判断当前字符串是否
是单词，是则成功；如果不是，反的trie后退到前一个是单词的位置，
正的trie前进到某位置使得正反两个串的长度和l，如果不成功则继续
直到反向字符串退回位置0
【在 b***e 的大作中提到】
: 搞两个tries, 一正一反，查两遍，比较长度，O(n).
:
: news,
: n.
: newspap, ne
: ewspaper, ws
: you ha
: is
|
|
