狗家超短电面

T大农民伯伯 发表于 2018-11-27 07:19
为啥不建个哈希表直接搜索word是否存在哈希表中。

那样的话复杂度也是NL？N是text长度，L是word_dict最长词长度。Trie的话如果匹配失败可以提前退出性能会好一点？储存的空间占用在非最坏情况也比hashmap好一点？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

PhantomFan 发表于 2018-11-28 04:51
嗯我也觉得是NL，然后我说的那个意思是，search for prefix的接口应该是找全所有存在于trie中的prefix， ...

明白了，谢谢！

T大农民伯伯 发表于 2018-11-28 06:00
如果用哈希表的话，我其实不知道时间复杂度有多大，我感觉是O(n). 因为你会把word字符串编码然后变成哈希 ...

对于长串每一个位置 从这里开始往前数1,2,...,L长的子串都需要判定是否在hashmap里。所以是NL？

PhantomFan 发表于 2018-11-28 07:42
对于长串每一个位置 从这里开始往前数1,2,...,L长的子串都需要判定是否在hashmap里。所以是NL？

我以为你再说热身题，之前分数不够看不到正式题，那确实是trie就可以了。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies