1. 问题描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2:
输入:s = “a”, t = “a”
输出:“a”
解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
2. 思路
题目要求寻找最小连续子串,那么第一个反应就是用滑动窗口求解。滑动窗口移动思路如下:
- 如果当前滑动窗口内没有涵盖t中的所有字符,那么窗口的右侧指针继续向右移动,扩大窗口。
- 如果当前滑动窗口内涵盖了t中的所有字符,那么窗口的左侧指针可以向右移动,缩小窗口,寻找最小子串,直到滑动窗口内无法涵盖t中的所有字符。
移动思路其实比较容易得到,那么还有几个问题:
- 由于t中会有重复字符,因此我们应该记录t中各个字符的数量。拿什么记录?
- 如何判断当前滑动窗口涵盖了t中的所有字符?
我一开始的思路是用HashMap,字符当作key,个数当作value。把字符串t和当前窗口都用两个Map表示。判断当前滑动窗口涵盖了t中的所有字符,就将两个map中的键值对都拿出来一一比较,只要当前窗口Map的value都大于等于t字符串,那就说明涵盖。但这样有个问题,我个人对map的遍历取值操作不太熟悉,而且感觉使用Map有点重,那么有没有别的数据结构可以代替呢?
突然想起来可以用数组,而且数组在存放时也可以达到O(1),在这道题和Map似乎没有差别。思路如下:
由于本题字符串中只有英文字母,因此我可以根据ASCII码,建立一个数组,数组长度就是’A’ - 'a’的值。这样,每一个字符就有固定对应的存放位置,可以保存他出现的次数。还是将字符串t和当前窗口都用两个数组表示。判断当前滑动窗口是否涵盖了t中的所有字符,那就只需要对两个数组进行比较,当前窗口的数组中的每个位置的元素都应该大于等于t字符串。这个操作就很简单了。
3. 代码
public String minWindow(String s, String t) {
//滑动窗口的左指针
int left = 0;
//记录最小字串的长度
int minLen = 100001;
//记录最小子串的起始位置
int start = 0;
//t字符串抽象成的数组,保存每一个字符出现的次数
int[] tArray = new int[58];
for(int i = 0; i < t.length(); i++) {
tArray[t.charAt(i) - 'A']++;
}
//当前滑动窗口抽象成的数组,保存每一个字符出现的次数
int[] temp = new int[58];
for(int right = 0; right < s.length(); right++) {
//先将这个字符加入到滑动窗口中
temp[s.charAt(right) - 'A']++;
//如果滑动窗口涵盖了字符串t
while(concludeT(temp, tArray)) {
//更新最小子串
if(minLen > right - left + 1) {
minLen = right - left + 1;
start = left;
}
//左指针向右移动
temp[s.charAt(left) - 'A']--;
left++;
}
}
return minLen == 100001 ? "" : s.substring(start, start + minLen);
}
//判断当前滑动窗口是否涵盖了t字符串
private Boolean concludeT(int[] temp, int[] tArray) {
for(int i = 0; i < temp.length; i++) {
if(temp[i] < tArray[i]) {
return false;
}
}
return true;
}