最小包含子串的长度
程序员文章站
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));
}
}