avatar
S*d
1
在Glassdoor看到的,条件不是特别清楚:
"Given a list of words with the same size and a big string that contains one
of the permutation of all the words combined (say p), find the startindex
of the string p in the big string."
大概用Trie可以做出来,不过有很多小edge case不知道怎么处理得好,比较说如果其
中一个string 的后缀是另一个的前缀好像会出现些问题。
还请各位大牛说说思路!
avatar
n*w
4
思路应该是这样。
tries判断是不是valid word,然后bit map判断是不是第一次出现。
复杂度O(nmL)。n是string长度,m是words数量,L是word长度。
用不用hashtable最好问interviewer。代价可能不低。

【在 d*******l 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/31974087.html
avatar
d*l
5
就是这意思,这样的话其实可以达到O(nL)。因为一共要枚举L个起始位置,每个位置扫
一遍就行。

【在 n*******w 的大作中提到】
: 思路应该是这样。
: tries判断是不是valid word,然后bit map判断是不是第一次出现。
: 复杂度O(nmL)。n是string长度,m是words数量,L是word长度。
: 用不用hashtable最好问interviewer。代价可能不低。

avatar
s*7
6
bless.
avatar
i*d
7

能详细说说这个题么? 我怎么觉得复杂度要O(nmL)? 还是我理解错了?

【在 d*******l 的大作中提到】
: 就是这意思,这样的话其实可以达到O(nL)。因为一共要枚举L个起始位置,每个位置扫
: 一遍就行。

avatar
m*q
8
darksteel这方法很赞啊,我开始只想出了O(nmL*lgm)的
我理解他的方法大概是这样的
先把big string分成长为L的段,一共有n/L段,在trie中查找
每一段需要O(L),共n/L段则需要 O(n)。用前后两个指针扫描
big string,用一个长度为m的数组标识当前在sliding window
中出现的段的index,如果发现重复的则递增后指针,否则递增
前指针,如果签后指针差为L的话则认为找到
因为分段可以从0,1,2,...L-1开始分,共有L种分法,所以
总的复杂度为O(nL)
不知道说明白了没有

【在 i**d 的大作中提到】
:
: 能详细说说这个题么? 我怎么觉得复杂度要O(nmL)? 还是我理解错了?

avatar
i*d
9
嗯,思路清楚了。
方法很赞,谢谢了~

【在 m**q 的大作中提到】
: darksteel这方法很赞啊,我开始只想出了O(nmL*lgm)的
: 我理解他的方法大概是这样的
: 先把big string分成长为L的段,一共有n/L段,在trie中查找
: 每一段需要O(L),共n/L段则需要 O(n)。用前后两个指针扫描
: big string,用一个长度为m的数组标识当前在sliding window
: 中出现的段的index,如果发现重复的则递增后指针,否则递增
: 前指针,如果签后指针差为L的话则认为找到
: 因为分段可以从0,1,2,...L-1开始分,共有L种分法,所以
: 总的复杂度为O(nL)
: 不知道说明白了没有

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。