360筆記試験のテーマ

本科の時にアルゴリズムの授業でこの問題を見たことがあることを覚えていて、その時はできなかったで、今日360の筆記試験をした時意外にもまだできていないで、本当に卵が痛いです.帰ってきて半日研究したが、私は拭いて、2時間でそんなに多くの問題をして、これはきっとできないに違いない.
タイトル:
文字列S:“BLFBFSYDLEAKLFBYM”とキーワードT:“LBY”を与えて、Sの中でTの最小文字列を含みますか?では、最小文字列「LFBY」を求めるべきです.
構想の1:Tを遍歴して、更にSを遍歴します.(どう見てもそうですが、操作が面倒で、私も実現していません)
考え方2:キーワードTの最初の文字と最後の文字がSの中の位置P 1,P 2をそれぞれ求めると、私たちが要求する答えはP 1とP 2の組み合わせの中にある.(余計なスペースを無駄にした)
道理によって、両方の考えが通じる.現在、私は構想2に従ってJava版を実現しています.
       

<span style="font-size:18px;">        </span><span style="font-size:14px;">
		public static void main(String []args)
			{
               final String content="BLFBFSYDLEAKLFBYM";
               final String key="LBY";
               System.out.println(getAbstract(content, key));
			}
		/*
		 * content="BLFBFSYDLEAKLFBYM"
		 * key="LBY"
		 *    key      
		 *   abstract L***Y,      L，    Y
		 */
		public static String getAbstract(String content,String key)
		{
			String tempString="";
//			 *      content L      Y     
//			 *              L    Y       
			ArrayList<Integer> keyFirstList=new ArrayList<Integer>();
			ArrayList<Integer>keyLastList=new ArrayList<Integer>();
			for(int i=0;i<content.length();i++)
				{
					if(content.charAt(i)==key.charAt(0))
						keyFirstList.add(i);
					else if(content.charAt(i)==key.charAt(key.length()-1))
						keyLastList.add(i);
					else
						;//do noting
				}
			//           
			//  ，         ，start      end   
			int [][]maxAbstact=new int[keyFirstList.size()][keyLastList.size()];
			for(int i=0;i<keyFirstList.size();i++)
				for(int j=0;j<keyLastList.size();j++)
					{
						if(keyFirstList.get(i)>=keyLastList.get(j))
							maxAbstact[i][j]=-1;
						else 
							{
								maxAbstact[i][j]=isContainKey(content, key, 
										keyFirstList.get(i), keyLastList.get(j));
							}
					}
			int minLength=content.length();
			int start = 0 ,end = 0;
			//         ，            
			for(int i=0;i<keyFirstList.size();i++)
				for(int j=0;j<keyLastList.size();j++)
					{
						if(maxAbstact[i][j]>-1&&maxAbstact[i][j]<minLength)
							{
								minLength=maxAbstact[i][j];
								start=i;
								end=j;
							}
					}
			for(int i=keyFirstList.get(start);i<=keyLastList.get(end);i++)
				{
				   tempString+=content.charAt(i);
				}
			return tempString;
		}
		/*
		 *  start  end       key
		 */
		public static int isContainKey(String content ,String key,int start,int end)
		{
			int newStart=start;
			for(int i=1;i<key.length()-1;i++)
				{
					int j=newStart+1;
					for(;j<end;j++)
						{
							if(content.charAt(j)==key.charAt(i))
								{
									newStart=j;
									break;
								}
						}
					if(j==end)
						return -1;
				}
			return end-start;
		}</span>