空气床电面 新题

空气床电面新题：

给一堆review list, for example:
[
"I like

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

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

quot;, "n"或者"c"].

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

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

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

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

用Trie,

1. Trie{
   
2.     string s;
   
3.     Trie * next[26];
   
4.     int idx; //idx -1, more than once
   
5. };

复制代码

首次插入新的分支，将review的index记下来，如果有其它review也走到这个分支，将idx写成-1，过完全部的review以后，再收集idx不为-1的分支

c不是都出现了？ 为什么输入c呢

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

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

cee 发表于 2020/02/17 11:25:06
c不是都出现了？ 为什么输入c呢

对对，不好意思看错了，c是不对的

gougou9903 发表于 2020/02/17 12:41:58
我觉得可以，PQ里可能需要加个对应review的index。我当时是直接遍历每个review. 然后每个review里的...

存每个单词 还是每个substring都要存？会不会空间太大了

先留爪

攒分赞好再看！

多谢多谢

顺手求米！

substring? 而且不考虑space， 比如“up to” sub strings 就是 u, p, t, o, up, pt, to, upt, pto? 如果不要每次重复check each review, 就要把所有sub string 放到pq 或 hashmap中了

suffix array

把所有的unique substring存起来。每个节点cnt，表示在多少entry里出现过