最短摘要（思路与题解）

最短摘要（思路与题解）

题目：

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

解释：

简单而言，基于两个String数组，再String的所有子集中，找到包含所有索引字符串的最短子数组的长度

思路:
设定两个指针begin与end，判断在他们之间的子数组是否包含索引索引字符串，如果包含则记录此时的长度，将begin向后移一格；如果不完全包含，则end向后一格，直到end超出范围

实现方法：
利用循环完成判断与移动，创建一个数组cun储存索引字符串的个数，begin每次移动便缩短了子数组，所以需要判断减少的字符串是否是索引字，是的话便要减少其数量，end每次移动都拓展了子数组，每次增加的字符串是索引字则要增加储存；创建了indexOf判断字符串是否在索引数组中，以及在哪个位置，从而便于改变cun储存数组的值

具体代码

public class 最短摘要 {
	public static void main(String[] args) {
		String [] leap= {"a","c","w","b","q","c","c","v","b","e","c"};//假定的字符串组
		String [] ind= {"a","b","c"};//假定的索引的字符串组
		int len=ind.length;
		int [] cun=new int [len];//储存索引的字符个数
		int min=leap.length-1;
		int begin = 0;
		int end = -1;//因为24行是先end++再处理，所以end要为-1，否则end=0会被跳过
		while (end<=leap.length-2) {//同理如果end=leap.length,end会超出索引值
			if (check(cun)) {
				int len1=end-begin+1;
				if (len1<min) min=len1;//取到此时的最短长度
				if (indexof(ind,leap[begin])==-1){
					begin++;
					continue;//如果不是关键字便进行下一轮循环
				}else {
					cun[indexof(ind,leap[begin])]--;
				    begin++;//如果是则去除cun中的储存
				}
			}else {//当储存不够时拓展end
				end++;
				if (indexof(ind,leap[end])!=-1) {
					cun[indexof(ind,leap[end])]++;
				}//找到关键字增加储存
			}
		}
		System.out.println(min);
	
	}
	
	public static boolean check(int [] arr) {//判断是否包含所有索引词
		for (int i=0;i<arr.length;i++) {
			if (arr[i]<1) {
				return false;
			}
		}
		return true;
	}
	

	public static int indexof(String [] arr,String a) {//搜索字符串在数组中的位置
		for (int i=0;i<arr.length;i++) {
			if (arr[i]==a) return i;
		}
		return -1;
	}
}