一道yelp电面题

找到了一个更详细的:
给一个String数组代表用户有很多bookmark,每个String可能是一个或者多个单词,需要在用户搜索输入一个字符串的时候返回所有包含这个字符串的bookmark
一开始是只返回字符串为prefix的bookmark,注意bookmark里如果有多个单词,第二个单词prefix符合也要返回这个bookmark
followup是如果不只是prefix, bookmark中任意地方符合就返回,注意一下大小写
followup2是问如果能储存一个让这种搜索加速的结构,用什么,

更详细的

bloom filter

这是substring match了吧

嗯嗯,是的是的

可以用 letter -> count的map做排除法吧

count的map是指???

我的意思是类似 bloom filter 的思路,你可以通过这种方式做排除法

有道理,就是用bloom filter来快速排除不存在的substring?

bloom filter的特性是出现过哪些 letter
substring还有连续 letter 的属性,这方面可以再想想

怎么感觉要kmp……