欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最小包含子串的长度

程序员文章站 2024-01-01 16:08:58
...

最小包含子串的长度

//最小包含子串的长度
public class MinSubStringLen
{     
	//给定字符串str1和str2,求str1的子串中含有str2所有字符的最小子串长度)
      public static int GetMinLen(String str1,String str2)
      {
      	if(str1==null||str2==null||str1.length()<str2.length())
      	{
      		return 0;
      	}
        char[]ch1=str1.toCharArray();
        char[]ch2=str2.toCharArray();
        int[]map=new int[256];       //充当hash表
        for(int i=0;i<ch2.length;i++)
        {
        	map[ch2[i]]++;
        }
        int left=0;
        int right=0;  
        int match=ch2.length;
        int minlen=Integer.MAX_VALUE;  //匹配到的最短长度
        while(right<ch1.length)
        {
            map[ch1[right]]--;
            if(map[ch1[right]]>=0)
            {
            	match--;
            }
            //匹配到字符串str2
            if(match==0)
            {    
            	//匹配了多个
            	while(map[ch1[left]]<0)
            	{
            		map[ch1[left++]]++;
            	}
                minlen=Math.min(minlen,right-left+1);  //获得最短的长度
                match++;
                map[ch1[left++]]++; //str1收回str2匹配到的位置
            }
             right++;
        }

        return minlen==Integer.MAX_VALUE?0:minlen;
      }
	    
	  public static void main(String []args)
	  {
          String str1="abcde";
          String str2="ac";

          String str3="adabbca";
          String str4="acb";

          System.out.println(GetMinLen(str1,str2));
          System.out.println(GetMinLen(str3,str4));

	  }
}
最小包含子串的长度

上一篇:

下一篇: