题11：最短摘要的生成

题目：

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

思路：

尺取法

package 字符串问题;

import java.util.Arrays;

public class case11_最短摘要的生成 {
    public static void main(String[] args) {
        solve(new String[]{"a","b","c","d","e","f","g","h","c"},new String[]{"a","b"});
    }
    public static void solve(String[] w,String[] keys){
        //begin和end记录包含关键词的最短数组
        int begin=-1;
        int end=-1;
        int p2=-1;//上一次囊括了所有关键词的有边界
        int minlen=Integer.MAX_VALUE;
        int[] keyFound=new int[keys.length];
        for(int i=0;i<w.length;i++){
            Arrays.fill(keyFound,0);
            //如果i位置是关键字，求出以i开头包含所有关键词的序列
            String word1=w[i];
            int index=indexof(keys,word1);
            if(-1==index){
                continue;
            }else{
                keyFound[index]=1;//标记为1
            }
            int j;
            if(p2!=-1){
                j=p2;
            }else{
                j=i+1;
            }
            for(;j<w.length;j++){
                String word2=w[j];
                int index1=indexof(keys,word2);
                if(-1==index1||keyFound[index1]==1){
                    continue;
                }else{
                    keyFound[index1]=1;//标记为1
                    if(sum(keyFound)==keys.length){//全部到齐
                        p2=j;
                        if(j-i+1<minlen){
                            minlen=j-i+1;
                            begin=i;
                            end=j;
                        }
                        break;
                    }
                }
            }
        }
        print(w,begin,end);
    }

    private static void print(String[] w, int begin, int end) {
        System.out.println( begin + " " + end);
        for(int i=begin;i<=end;i++){
            System.out.print(w[i]+" ");
        }
        System.out.println();
    }

    private static int sum(int[] keyFound) {
        int sum=0;
        for(int e:keyFound){
            sum+=e;
        }
        return sum;
    }

    /**
     * word在不在关键词里面
     * @param keys
     * @param word1
     * @return
     */
    public static int indexof(String[] keys,String word1){
        for(int i=0;i<keys.length;i++){
            if(keys[i].equals(word1)){
                return i;
            }
        }
        return -1;
    }

}