骨骼 店面

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。。。？

遍历全部的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吧？

楼主感觉很难吗