这个题依旧是滑动窗口 + 哈希表,只不过多了几个细节。首先是滑动窗口的大小,是不确定的,可能很短,可能很长,也可能为0。那什么是判断的条件呢?
我们用hash表,遍历 t 数组,之后再遍历 s 数组,对比s和t数组,从而得出满足条件的字符串。
但是如果只是这样,还是不够,因为缺少了判断条件,我们用count来记录当前有效字符的种类,以示例一为例子,t的有效字符就是ABC,也就是3种,那么我们判定s的字符种类也为3的时候,就说明当前字符串是符合要求的字符串。
首先在遍历 t 数组的时候,我们用一个kinds来记录当前有效字符的种类,这样判断的时候,只需要判断count == kinds的时候,就能符合题目要求。
但是仅仅引入count和kinds还不够,我们还需要引入一个begin和最小长度minlen,只有当minlen是最小的时候,才符合题目要求,begin则是记录当前开始的left指针的位置。
之后则是进窗口、出窗口的滑动窗口经典的操作了,要注意count加减的条件和细节问题。
代码:
class Solution {
public String minWindow(String s, String t) {
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
int[] hash2 = new int[128];
int kinds = 0;
for(char ch : tt){
if(hash2[ch]++ == 0){
kinds++;
}
}
int[] hash1 = new int[128];
int minlen = Integer.MAX_VALUE;
int begin = -1;
for(int left = 0, right = 0, count = 0; right < ss.length; right++){
char in = ss[right];
hash1[in]++;
if(hash1[in] == hash2[in]){
count++;
}
while(count == kinds){
if(right - left + 1 < minlen){
begin = left;
minlen = right - left + 1;
}
char out = ss[left++];
if(hash1[out]-- == hash2[out]){
count--;
}
}
}
if(begin == -1){
return new String();
}else{
return s.substring(begin, begin + minlen);
}
}
}