0%

列出的解答仅为自己的思路,仅供参考,欢迎指出错误。

题目Wiki及参考答案

http://www.algorithm.cs.sunysb.edu/algowiki/index.php/Sorting-searching-TADM2E

我的解答

面试问题

4-45

题目

Given a search string of three words, find the smallest snippet of the document that contains all three of the search words—i.e., the snippet with smallest number of words in it. You are given the index positions where these words occur in the document, such as word1: (1, 4, 5), word2: (3, 9, 10), and word3: (2, 6, 15). Each of the lists are in sorted order, as above.

解答

每个单词出现的位置列表都是有序的,将它们看做是队列。设定min_len保存当前最短的片段的长度,初始化为-1.算法步骤如下:

  1. 若各队列不空,将各队列最小元素出队,组成三元组
  2. 得三元组(a1, a2, a3)
  3. 求三元组中的最大值max,与最小值min,则当前片段长度len = max-min+1
  4. 如果min_len为-1或min_len大于lenmin_len = len,保存三元组.
  5. 删除三元组中最小者min,若min对应队列不空,取新元素加入到三元组,执行2,若空,退出循环。
变形及分析

变形

假设输入数据不是3个单词的出现位置,而直接是一个字符串数组,那么如何找到满足要求的最小片段?

分析

cur为访问数组的当前位置,3个变量l1, l2, l3,代表cur前面离cur最近的3个单词(w1, w2, w3)的位置。若cur上的单词为3个单词之一,不妨设为w3,则计算w3与w1,w2的距离即cur-l1+1cur-l2+1,取小者为min,另minmin_len比较,若min更小,保存min,及当前3个单词的位置。当遍历数组结束时,最后的min_len与保存的3元素的位置即满足要求的最小片段。

阅读全文 »