最短摘要的生成

分而治之

Posted by Yinode on Wednesday, May 5, 2021

TOC

最近好久没写文章了,大量的时间都花在了刷LeetCode上,最近开始重拾博客。

最短摘要

假设我们拥有一个分词数组W = [w1,w2,w3,w4,w5…] 并拥有一个query数组 Q= [q1,q2,q3…], 求w的中一个sub array, sw 内部包含我们所有的query子项,并要求是所有满足条件的sub array中最短的一个。

举个例子 W = [‘a’, ‘b’, ‘c’, ‘1’, ’d', ‘e’, ‘2’, ‘f’, ‘g’, ‘1’, ‘h’, ‘2’] Q = [‘2’,‘1’] 其最短摘要为 [‘1’,‘h’,‘2’] = length(3)

这个问题是在《编程之美》中看到的,书中有描述解法,但是不是特别完整, 我这里做了具体实现并进行一下简单解释

解法1 暴力

第一种解法就是从w1开始搜索W数组,一直到包含所有我们的关键词为止,我们记录下他的最短摘要长度,然后从w2开始,重新开始搜索,反复重复,直到找出最短摘要的长度为止,复杂度为(N ^ 2 * m)

解法2 建立前后关联

[‘a’, ‘b’, ‘c’, ‘1’, ’d', ‘e’, ‘2’, ‘f’, ‘g’, ‘1’, ‘h’, ‘2’]

第二种方法的核心在于建立起搜索之间的关联,

  1. 我们假设中w1也就是’a’开始搜索,一直到满足我们的摘要结束,完成我们第一次的搜索 这时候的结果应该为 [‘1’, ’d', ‘e’, ‘2’] = Length(4)
  2. 这时候我们进行第二次搜索 把搜索位置变成上一次摘要起始的索引+1开始,也就是 ’d' 的位置 这里的关键在于我们利用了上一次的搜索结果
  3. 如此反复

代码的实现有几点关键,第一是要记录我们摘要的起始位置,方便下次循环作为起始标识,第二是可以利用一个Map来存放当前从start到end这个区间内部到底包含了多少关键词,通过空间换时间

下面是具体代码

const minAbs = (words, query) => {
  let n = words.length
  let start = 0
  let end = 0
  let firstFoudIndex = -1
  let minStart = 0
  let minEnd = 0
  let minAbsRange = Infinity

  // 建立查询是否是目标关键词的Map O(1)查询时间 空间换时间
  let queryMap = new Map()
  query.forEach((element) => {
    queryMap.set(element, true)
  })
  let containMap = new Map()

  while (true) {
    if (end >= n) break

    // 检查END指针是否指向一个存在的关键词
    // 如果属于关键词,那么放入start - end 区间的关键词列表Map中
    // 如果是start - end 区间内的第一个关键词 记录其索引
    if (queryMap.has(words[end])) {
      containMap.set([words[end]], true)
      if (firstFoudIndex === -1) firstFoudIndex = end
    }

    // 区间内并未包含所有关键词 继续向下搜索
    if (containMap.size < queryMap.size) {
      end++
    } else if (containMap.size === queryMap.size) {
      // 包含所有关键词 检测是否是更短的区间长度
      if (end - firstFoudIndex < minAbsRange) {
        minStart = firstFoudIndex
        minEnd = end
        minAbsRange = end - firstFoudIndex + 1
      }
      // 重置所有属性
      // 下次搜索将会从这次搜索的第一个关键词所在的位置+1的地方上继续搜索
      start = firstFoudIndex + 1
      end = firstFoudIndex + 1
      firstFoudIndex = -1
      containMap.clear()
    }
  }

  console.log(minStart, minEnd, minAbsRange)
  return minAbsRange
}

console.log(minAbs(['a', 'b', 'c', '1', 'd', 'e', '2', 'f', 'g', '1', 'h', '2'], ['2', '1']))

总结

在构建最优算法的过程很难直接找到一个最优解,所以不妨从一个不够好的暴力算法开始,不断优化,提升,提炼问题本质,方能找到更好的算法替代,如此反复,才是算法编程之真谛。