最短摘要的生成

Bertha 。 2022-03-20 11:58 179阅读 0赞

Alibaba笔试题：

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

这个问题和编程之美3.5的题目类似，就是在字符串description中找一段包含keywords数组中所有字符串关键字的字符串。

思路：利用两个索引分别指向我们最终生成的摘要的位置，接下来进行如下循环：（1）首先判断摘要中是否包含所有关键字，如果不全包括，则将遍历的尾标志向后加1，直到包含所有关键字都被包含或者尾标志超出范围。（2）接下来将遍历的首标志向后移动，并不断检查移动过程中摘要是否还是全部被包含，如果被全部包含，说明存在长度更小的摘要，这时需要更新最短摘要的长度及下标位置；如果再移动过程中发现不全部包含了，则继续（1）的操作，直到尾标志超出范围。

算法实现如下所示：

package com.part3;
    import java.util.Map;
    import java.util.HashMap;
    //最短摘要生成
    public class Abstract {
    	private int[] keywordsCount;//记录关键字被访问的次数
    	private int pstart=0,pend=0;//定义查找起始点和终点
    	private int astart=0,aend=0;//定义摘要起始点和终点
    	private int abstractlen=0;//摘要长度
    	private Map<String,Integer> map;//定义关键字到访问次数的映射
    	public Abstract(String[] keywords)
    	{
    		int len=keywords.length;
    		keywordsCount=new int[len];
    		map=keywordsMap(keywords);
    	}
    	public String extractSummary(String source,String[] keywords)
    	{
    		String[] src=source.split(" ");
    		return extract(src,keywords);
    	}
    	public String extract(String[] source,String[] keywords)
    	{
    		int len=source.length;
    		abstractlen=len+1;
    		while(true)
    		{
    			while(!isAllExisted()&&pend<len)
    			{
    				if(this.map.get(source[pend])!=null)
    				{
    					setKeywordsCount(this.map.get(source[pend]),false);
    				}
    				pend++;
    			}
    			while(isAllExisted())
    			{
    				if(pend-pstart<abstractlen)
    				{
    					abstractlen=pend-pstart;
    					astart=pstart;
    					aend=pend-1;
    				}
    				if(this.map.get(source[pstart])!=null)
    				{
    					setKeywordsCount(this.map.get(source[pstart]),true);
    				}
    				pstart++;
    			}
    			if(pend>=len)
    				break;
    		}
    		StringBuilder summary=new StringBuilder();
    		for(int i=astart;i<aend;i++)
    		{
    			summary.append(source[i]+" ");
    		}
    		summary.append(source[aend]);
    		return summary.toString();
    	}
    	private Map<String,Integer> keywordsMap(String[] keywords)//将关键字和其索引构成映射关系
    	{
    		Map<String,Integer> map=new HashMap<String,Integer>();
    		int len=keywords.length;
    		for(int i=0;i<len;i++)
    		{
    			map.put(keywords[i], i);
    		}
    		return map;
    	}
    	private void setKeywordsCount(int i,boolean flag)//flag为false时次数减1,为true时次数加1
    	{
    		if(flag)
    			this.keywordsCount[i]++;
    		else
    			this.keywordsCount[i]--;
    	}
    	private boolean isAllExisted()//判断关键字是否都包含
    	{
    		boolean res=true;
    		for(int count:keywordsCount)
    		{
    			if(count==0)
    			{
    				res=false;
    				break;
    			}
    		}
    		return res;
    	}
    	//测试用例
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		String description="hello software hello test world spring sun world flower hello";
            String[] keywords = {"sun","flower"};
            Abstract nAbstract = new Abstract(keywords);
            System.out.println(nAbstract.extractSummary(description, keywords));
    	}
    
    }

代码测试结果如下所示：

sun world flower

运行结果满足题意，既包含所有关键字，长度也最短。