📣 独立日限时特惠: VIP通行证立减$68
12
返回列表 发新帖
楼主: mayborin
跳转到指定楼层
上一主题 下一主题
收起左侧

骨骼 店面

全局:
pandami 发表于 2019/05/17 06:55:30


Word trie明白吗?区别就是每个node有个hashtable存str 结尾node还要存tuple id
先把所有词存成trie 第一步Omn复杂度
然后从每个tuple的每个词开始查字典...

感觉非常暴力...要建trie还要保证每个list都是sorted的吧 建trie就是O(M*N*L*logN) L是单词avg长度 最后 overall O(MLN^2)

补充内容 (2019-5-17 07:52):
不好意思最后多打了一个L overall O(MN^2)
回复

使用道具 举报

全局:
iiimisery 发表于 2019/05/17 07:49:49


感觉非常暴力...要建trie还要保证每个list都是sorted的吧 建trie就是O(M*N*L*logN) L是单词avg长度 最后 overall O(MLN^2)

补充内容 (2019...

不需要sorted 最后是mnn

补充内容 (2019-5-17 09:35):
实际上大部分情况会提前截断
应该不到nn
回复

使用道具 举报

全局:
iiimisery 发表于 2019/05/17 07:49:49


感觉非常暴力...要建trie还要保证每个list都是sorted的吧 建trie就是O(M*N*L*logN) L是单词avg长度 最后 overall O(MLN^2)

补充内容 (2019...

哈哈 我觉得比较好写
要不然就是某种rolling hash。。。?
回复

使用道具 举报

🔗
sdnbig 2019-5-17 09:52:39 | 只看该作者
全局:
遍历全部的input,建立一个hashtable, {string:set(names)}

比如
[
("A", [ "abc", "bc", "de"]),
("B", [ "abc", "de"]),
("C", [ "bc"]),
]

=> {
"abc" : (A, B)
"de" : (A, B)
"bc' : (A, C)
}

然后再遍历input, 求每个string对应名字的交集,
如果是(B, A, C), 就是结果,还要一个de-dup + combination

TC: O(n),
SC: O(n),
n is # of word
回复

使用道具 举报

全局:
pandami 发表于 2019/05/17 09:31:44


不需要sorted 最后是mnn

补充内容 (2019-5-17 09:35):
实际上大部分情况会提前截断
应该不到nn

应该要sort吧 比如lz的例子 a变成3 2 1

补充内容 (2019-5-17 14:20):
......不对 不用sort 没看到题目是subarray
回复

使用道具 举报

全局:
sdnbig 发表于 2019/05/17 09:52:39
遍历全部的input,建立一个hashtable, {string:set(names)}

比如
[
("A", [ "abc", "bc", "de"]),
("B", [ "abc"...

这个好像只能找到subset不能找subarray吧?
回复

使用道具 举报

🔗
tuwei 2019-5-22 16:55:18 | 只看该作者
全局:
楼主感觉很难吗
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表