现在的位置: 首页 > 综合 > 正文

203 最短摘要生成

2018年01月19日 ⁄ 综合 ⁄ 共 405字 ⁄ 字号 评论关闭

3.  Alibaba 笔试题:给定一段产品的英文描述,包含 M 个英文字母,每个英文单词以空格分隔,无其他标点符号;再给定 N 个英文单词关键字,请说明思路并编程实现方法
String extractSummary(String description,String[] key words)目标是找出此产品描述中包含N个关键字(每个关键词至少出现一次)的长度最短的子串,作为产品简介输出。(不限编程语言)20 分。

扫描过程始终保持一个[left,right]的 range,
初始化确保[left,right]的range里包含所有关键字则停止。
然后每次迭代:
1,试图右移动left,停止条件为再移动将导致无法包含所有关键字。
2,比较当前range's length 和 best length,更新最优值。
3,右移right,停止条件为使任意一个关键字的计数+1。
4,重复迭代。 
编程之美有最短摘要生成的问题,与此问题类似,读者可作参考。 )

抱歉!评论已关闭.