#每日一面BAT#第12题 文章与词


给定一篇文章,可以简单把文章理解为词的列表(不考虑标点、大小写等)。再给定一个word的集合,求文章中尽可能短的一个片段(包含词个数尽可能少),包含集合里全部的词 (不一定按顺序)。
已邀请:

cpcs - 诚实努力

赞同来自:


答案: 对词建立倒排索引。
即 建立list
word1: p1,1, p1,2, p1,3...
word2: p2,1, p2,2, p2,3...
word3:...

word后面的列表表示这个词出现的位置。
假设要包含n个词,设置n个指针,从每个词的列表头开始指向。
可行的答案是max(P) - min(P)。
然后类似归并排序,每次移动位置最小的指针,让它沿着列表指向后一个位置……
如此不断移动指针,直到有一个列表走到末尾即可。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~