Google onsite

coldknight · 2016-12-19 23:49:47

stellari 发表于 2016-12-15 03:44
关于第一题的优化，我想可不可以这样：不对字典里的单词建trie，而是对target建这样一个数据结构：即，对ta ...

对target建trie不是一样的吗？预处理应该是O(2^len(target))吧？

stellari · 2016-12-20 06:35:15

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

laiguojiuhao · 2016-12-20 11:30:35

stellari 发表于 2016-12-15 03:44
关于第一题的优化，我想可不可以这样：不对字典里的单词建trie，而是对target建这样一个数据结构：即，对ta ...

大神你这个解法是不是有点像suffix tree啊

stellari · 2016-12-21 02:40:21

laiguojiuhao 发表于 2016-12-20 11:30
大神你这个解法是不是有点像suffix tree啊

其实基本上就是suffix tree，只是不存完整的suffix，而是只存unique字符第一次出现的位置

donnice · 2016-12-21 02:49:34

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

zzgzzm · 2016-12-21 04:24:15

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

zzgzzm · 2016-12-21 04:32:50

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

laiguojiuhao · 2016-12-21 06:00:19

https://discuss.leetcode.com/topic/57151/3-lines-c/5
这个帖子里有O(len(t) + sum(len(s)))的方法

zzgzzm · 2016-12-21 09:46:41

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

zzgzzm · 2016-12-21 13:03:29

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