b******7 发帖数: 79 | 1 就是一直一篇文章,球可以覆盖所有单词的最小窗口,记得bbs有几个人提过这个题,
但是没人给过解,希望牛人能够赐教!!感激! | g*******y 发帖数: 1930 | 2 haven't read this one before, would you mind explain the problem in a little more details? | a*****e 发帖数: 51 | 3 What does 'the smallest window' mean? Dose it mean that within this window, every unique words appear? If it is the case, then the following solution attacks:
Build a suffix tree for the text, each node contains a link list of
positions of the corresponding words in ascending order. So you would have something like:
Node1: 4->12->27->30->...
Node2: 14->22->37->40->...
Node3: 2->5->12->28->...
.
Node M: 12->13->27->32->... M be the #of unique words
Maintain a variable MinD for the current minimu
【在 b******7 的大作中提到】 : 就是一直一篇文章,球可以覆盖所有单词的最小窗口,记得bbs有几个人提过这个题, : 但是没人给过解,希望牛人能够赐教!!感激!
|
|