LeetCode -- 76. 最小覆盖子串

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']++;//如果滑动窗口涵盖了字符串twhile(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;}